[Greedy] 최소 신장 트리(Minimum Spanning Tree)

최소 신장 트리가 무엇인지, 그리고 최소 신장 트리를 만들기 위한 효율적인 알고리즘에 대해 알아보겠다.

 

1. 최소 신장 트리(Minimum Spanning Tree)

최소 신장 트리는 Weighted, Undirected Graph에서 필요한 개념이다.

weighted란 각 Edge마다 가중치가 다르고, Undirected는 방향이 없다는 것이다.

방향이 없다는 것은 Vertex A에서 Vertex B로 가는 가중치와 Vertex B에서 Vertex A로 가는 가중치가 항상 같다는 것이다.

 

신장 트리는 그래프에서 최소한의 Edge만을 가지는 연결 부분 그래프이다.

그리고 MST(최소 신장 트리)는 신장 트리 중, weight의 합이 가장 작은 그래프를 의미한다.

 

MST를 구하는 것은, 최단 거리를 구하는 등 매우 유용하게 쓰인다.

(OSPF 프로토콜 등)

그리고 가장 효율적으로 구하는 방법은 탐욕적 알고리즘 (Greedy Algorithm)을 사용하는 것이다.

Greedy Algorithm이 성립하는 증명은 참조 책을 참고하기 바란다.

 

2. 프림 알고리즘(Prim's Algorithm)

 

A의 Vertex의 집합 V {v1, v2, ... , vn),

V의 부분집합 Y (Y의 초깃값은 {v1}, 

Edge의 집합 F (F의 초깃값은 {})

 

Y에서 V-Y 중 가장 가까운 Edge를 선택한다.

그 Edge에 해당하는 vertex를 Y에 edge를 F에 추가한다.

Y == V면 동작을 멈춘다. 이 때, 선택된 F가 A의 최소 신장 트리의 edge 집합이다. 

 

3. 크루스칼 알고리즘(Kruscal's Algorithm)

 

각 Edge들의 서로소 집합을 만든다.

가장 작은 가중치를 가지는 Edge부터 그래프에 포함시킨다.

만약 그 Edge가 루프를 형성한다면, 제외한다.

같은 가중치를 가진다면 임의의 한 Edge를 포함한다.

모든 Vertex가 포함되면 종료한다.

 

4. 프림 알고리즘과 크루스칼 알고리즘의 비교

n: vertex의 개수, m: edge의 개수

Spase Graph : Edge의 갯수가 하한에 가까운 그래프

Dense Graph : Edge의 갯수가 상한에 가까운 그래프

	W(m,n)	저밀도 그래프(sparse graph)	고밀도 그래프(dense graph)
Prim	Θ(n^2)	Θ(n^2)	Θ(n^2)
Kruscal	Θ(mlgm) and Θ((n^2)lgn)	Θ(mlgm)	Θ((n^2)lgn)

따라서, 저밀도 그래프에서는 Kruscal 알고리즘, 고밀도 그래프에서는 Prim 알고리즘이 효율적이다.

시간복잡도 계산은 참조의 책을 참고하기 바란다.

 

참조)

Richard E. Neapolitan. (2014). Foundations of Algorithms (5/E)