Kruskal's Algorithm

1정의#

가중치 그래프 G = (V, E)의 최소 신장 트리(MST)는 간선 가중치 합이 최소인 신장 트리이다.

크루스칼 알고리즘은 간선을 가중치 오름차순으로 정렬한 뒤, 사이클을 만들지 않는 간선을 차례로 선택하여 MST를 구성한다.

2알고리즘#

1. E의 간선을 가중치 오름차순으로 정렬한다: e₁, e₂, ⋯, e_m (w(e₁) ≤ ⋯ ≤ w(e_m)).
2. 각 정점을 독립된 집합으로 초기화한다.
3. e_i를 순서대로 검사하여, 양 끝점이 다른 집합에 속하면 MST에 추가하고 두 집합을 합친다.
4. MST의 간선 수가 n − 1이 되면 종료한다.

3증명#

크루스칼 알고리즘이 MST를 생성함을 |V|에 대한 귀납법으로 증명한다.

기저 (|V| = 1): 단일 정점이 MST이고, 크루스칼은 아무것도 선택하지 않는다.

귀납 (|V| > 1): 크루스칼이 처음 선택하는 간선 e는 G의 최소 가중치 간선이다. e를 포함하지 않는 MST T가 있다면, T에 e를 추가하면 사이클이 생기고 이 사이클의 다른 간선 e'는 w(e') ≥ w(e)이다. T에서 e'를 e로 교체하면 e를 포함하는 MST T^*를 얻는다. G/e는 정점이 |V|−1개이므로 귀납 가설에 의해 크루스칼은 G/e의 MST를 생성한다. G에서 e 이후의 선택은 G/e에서의 선택과 동일하므로, 크루스칼의 최종 출력 F는 e를 포함하는 신장 트리이다. G의 신장 트리 중 e를 포함하는 것은 G/e의 신장 트리와 일대일 대응되므로, F는 e를 포함하는 신장 트리 중 가중치 합이 최소이다. w(F) ≤ w(T^*)이고 T^*는 MST이므로 F도 MST이다. ■

4시간 복잡도#

단계	시간 복잡도
간선 정렬	O(m log m)
Union-Find	O(m · α(n))
합계	O(m log m)

5참고 문헌#

• Kruskal, J. B. (1956). On the shortest spanning subtree of a graph and the traveling salesman problem. Proceedings of the American Mathematical Society, 7(1), 48–50.