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)]. 매우 느리게 증가하는 함수로 이해하면 된다.