알고리즘 이론 23강. 최소 신장 트리(MST)

 

[신장트리와 신장숲]

1. 신장 트리(Spanning Tree)

  : 그래프의 정점들을 가지고 있는 트리(연결되고, 순환아닌 특징)

2. 신장 숲(Spanning forest)

  : 그래프가 연결되어 있지 않을때, 신장 트리를 만들수 없다. 대신 신장 숲을 만들 수 있다.

  : 각 연결된 요소들이 신장트리들을 가짐 = 여러개의 부분 신장트리의 느낌

 

# 신장 트리와 신장 숲 예시

 

 

 

[최소 신장 트리(MST)]

: 신장 트리중 가중치의 합이 최소가 되는 신장 트리

: 유일하지 않다 ( 정점 연결방식 달라도 최소 비용이 동일한 트리 있는 경우 )

: 경로 연결간에 가장 저렴한 경로를 찾는데 사용되곤 한다.

: 허프만 코드와 마찬가지로 매우 유명한 그리디 알고리즘중 하나이다.

 

# 최소 신장 트리의 특성

  : MST 여러개 존재 가능 (유일하지 않다)

  : 순환되면 안된다

  : MST의 edge의 개수 = |V(정점)| - 1

 

 

 

[최소 신장 트리 구하기 1 - Prim's MST 알고리즘]

1) 우선 어떤 형태로든 트리 하나를 만든다.

2) 루트 r에서 시작해서, 현 단계에서 갈수 있는 모든 곳 검색해 가장 저렴한 곳 연결한다 (이때 순환 안되게끔)

: 우선순위 큐를 이용한다.

 

# Prim's MST 알고리즘 예시

: 우선순위 큐에 현재 까지의 노드중에서 갈 수 있는 노드(순환안되는 가정하에) 들의 비용들을 가지고 있어 이중에 최소 값을 추출해 연결한다.

  (연결 가능한 노드 목록에서 이미 트리에 있는 노드는 제외된다 - 순환 방지)

 

 

 

[최소 신장 트리 구하기 2 - Kruskal's MST 알고리즘]

1) 우선 전체 가중치를 스캔한다.

2) 가중치들중에서 가장 작은 edge부터 그리는데 순환되지 않는 하에서 연결한다.

 

# kruskal의 MST 알고리즘 예시