최소 비용 신장 트리

1. 개요2. 알고리즘

2.1. 프림 알고리즘 (Prim's algorithm)2.2. 크루스칼 알고리즘 (Kruskal's algorithm)

3. 둘러보기

1. 개요

Minimum Spanning Tree, MST

신장 트리는 그래프에서 모든 정점에 대한 최소한의 연결만을 남긴 그래프이다. 한 곳으로 도달하는 경우가 두 개 이상 존재하는 경우, 즉 사이클이 존재하는 경우에는 최소한의 연결이라 말할 수 없기 때문에, 모든 위치 하나에서 다른 곳으로 이동하는 경우는 단 한 가지로 결정되도록 항상 트리의 형태를 나타낸다. 최소 비용 신장 트리는 이러한 신장 트리들 중 간선의 가중치 합이 가장 작은 트리이다.

2. 알고리즘

최소 비용 신장 트리는 그리디 기법을 이용하여 최적의 해를 구할 수 있으며, 크루스칼 알고리즘과 프림 알고리즘, 솔린 알고리즘이 알려져 있다.

프림 알고리즘은 바이너리 힙을 이용하는 경우 [math(O(|E|+|V| log |V|))]의 시간 복잡도를 가지며, 크루스칼 알고리즘은 경로 최적화를 이용하지 않는 경우 [math(O([E| log |V|))], 경로 최적화를 이용하는 경우 [math(O([E| log^* |V|))][1]의 시간 복잡도를 가지기 때문에, 그래프의 간선 밀도를 고려하여 최적의 알고리즘을 선택하는 것이 필요하다.