1. 개요
Minimum Spanning Tree, MST신장 트리는 그래프에서 모든 정점에 대한 최소한의 연결만을 남긴 그래프이다. 한 곳으로 도달하는 경우가 두 개 이상 존재하는 경우, 즉 사이클이 존재하는 경우에는 최소한의 연결이라 말할 수 없기 때문에, 모든 위치 하나에서 다른 곳으로 이동하는 경우는 단 한 가지로 결정되도록 항상 트리의 형태를 나타낸다. 최소 비용 신장 트리는 이러한 신장 트리들 중 간선의 가중치 합이 가장 작은 트리이다.
2. 알고리즘
최소 비용 신장 트리는 그리디 기법을 이용하여 최적의 해를 구할 수 있으며, 크루스칼 알고리즘과 프림 알고리즘, 솔린 알고리즘이 알려져 있다.프림 알고리즘은 바이너리 힙을 이용하는 경우 [math(O(|E|+|V| log |V|))]의 시간 복잡도를 가지며, 크루스칼 알고리즘은 경로 최적화를 이용하지 않는 경우 [math(O([E| log |V|))], 경로 최적화를 이용하는 경우 [math(O([E| log^* |V|))][1]의 시간 복잡도를 가지기 때문에, 그래프의 간선 밀도를 고려하여 최적의 알고리즘을 선택하는 것이 필요하다.
2.1. 프림 알고리즘 (Prim's algorithm)
2.2. 크루스칼 알고리즘 (Kruskal's algorithm)
3. 둘러보기
[1]
[math(log^* n)]: [math(n)]이 1 아래로 될 때 까지의 log 수행 횟수. 예) [math(log log log log 1000 \le 1)]이기 때문에 [math(log^* 1000 = 4)]. 매우 느리게 증가하는 함수로 이해하면 된다.