[자료구조][알고리즘] Kruskal's Algorithm(크루스칼 알고리즘)

1. Kruskal's Algorithm이란?

Kruskal's Algorithm(크루스칼 알고리즘)은 그래프를 공부할 때 함께 배웠던 minimum cost spanning tree(최소 스패닝 트리)를 구하는 방법 중 하나이다.
간단히 설명하면, 그래프의 edge를 모두 제거한 후, 각 edge의 cost를 오름차순으로 정렬한다. 그리고 제일 cost가 작은 edge부터 그래프의 노드에 다시 붙이는데, 이 과정에서 cycle이 생긴다면(트리가 만들어지지 않는다면) 붙이지 않는다. 이러한 순서를 반복하여 최소 스패닝 트리를 만드는 알고리즘이다.

2. Kruskal's Algorithm의 Pseudo code

Start with an empty set T of edges.
while (E is not empty && |T| != n-1) {
	Let (u, v) be a least-cost edge in E.
    E = E - {(u, v)}.
    if ((u, v) does not create a cycle in T)
    	Add edge (u, v) to T.
}
if (|T| == n-1)
	T is a min-cost spanning tree.
else
	Graph has no spanning tree.

3. 예시

예를 들어, 위 그림과 같은 그래프가 있다고 하자. 크루스칼 알고리즘을 이용해 이 그래프의 최소 스패닝 트리를 구할 것이다.
그러기 위해 먼저 그래프의 edge를 모두 제거하고, edge를 cost 오름차순으로 정렬했다.

cost가 작은 edge부터 하나씩 추가하다가, cost가 8인 (1, 3) edge를 추가하려고 하자 1, 2, 3 노드에서 cycle이 생기는 것을 확인할 수 있었다. cycle이 있으면 tree가 아니기 때문에, 이 edge는 추가하지 않는다.

이번에는 cost가 9인 (2, 4) edge를 추가하려고 하였으나, 2, 3, 4 노드에서 cycle이 생기는 것을 확인할 수 있었다. 따라서 이 edge도 추가하지 않는다.

같은 이유로, cost가 12인 (3, 6) edge도 추가하지 않는다.

크루스칼 알고리즘을 이용하여 최종적으로 완성한 최소 스패닝 트리는 위 그림과 같다.

4. 시간복잡도

• 초기화: $O(n)$
• 최대 2e번의 탐색과 n-1번의 unions: $O(n+e)$
• cost를 오름차순으로 정렬하기 위해 min heap 사용: $O(e\log e)$
• 전체 시간복잡도: $O(n+e\log e)$