크러스컬 알고리즘

컴퓨터 과학에서 크러스컬 알고리즘(영어: Kruskal’s algorithm)은 최소 비용 신장 부분 트리를 찾는 알고리즘이다. 변의 개수를 $E$, 꼭짓점의 개수를 $V$라고 하면 이 알고리즘은 ${\color {Blue}O}(E\log V)$의 시간복잡도를 가진다.

개요

크러스컬 알고리즘은 아래의 순서대로 작동한다.

1. 그래프의 각 꼭짓점이 각각 하나의 나무(자료구조의 tree)가 되도록 하는 숲 F을 만든다.
2. 모든 변을 원소로 갖는 집합 S를 만든다.
3. S가 비어있지 않는 동안
   1. 가장 작은 가중치의 변을 S에서 하나 빼낸다.
   2. 그 변이 어떤 두 개의 나무를 연결한다면 두 나무를 연결하여 하나의 나무로 만든다.
   3. 그렇지 않다면 그 변은 버린다.

알고리즘이 종료됐을 때 숲 F는 하나의 최소 비용 신장 부분 그래프만을 가지게 된다.

크러스컬 알고리즘의 다른 형태가 있다. 이것은 그래프에서 변을 제거하는 방식이다.

1. 그래프에서 꼭짓점 또는 나무를 분리해 내지 않는 최대 가중치의 변을 제거한다.
2. 그래프에 n-1개의 변만 남을 때까지 1을 반복한다.
3. 그래프에 n-1개의 변이 남으면 최소 비용 생성나무이다.

알고리즘

$E$를 변의 개수라 하고, $V$를 꼭짓점의 개수라고 하자. 크러스컬 알고리즘은 ${\color {Blue}O}(E\log V)$ 시간 안에 동작한다고 증명될 수 있다. 간단한 자료 구조가 쓰인다면 $O(E\log V)$ 안에 동작한다. 이 동작 시간은 동일한데, 그 까닭은 다음과 같다:

• $E$는 최대 $V^{2}$ 개일 수 있다. $\log V^{2}=2\log V$는 $O(\log V)$이다.
• 홀로 떨어진 꼭짓점들을 무시한다면 (그들 각각은 그만의 최소 비용 신장 부분 그래프가 된다.), $V\leq 2E$이다. 그러므로 $\log V$는 $O(\log E)$이다.

이러한 시간 복잡도 한계는 다음과 같은 방법으로 도달할 수 있다. 변들을 그 가중치 순으로 $O(E\log E)$ 시간 내에 정렬한다. 정렬을 함으로써, "집합 S로부터 최소 가중치를 갖는 변을 제거한다"는 동작이 상수 시간에 행해질 수 있게 된다. 서로소 집합 자료 구조(유니온 파인드: 결합과 검색)를 이용하여 어떤 꼭짓점이 어떤 콤포넌트(component)에 속하는 지 추적한다. 디스조인트-셋 찾기(find) 동작 두 번에 $O(E)$ 시간이 걸린다. 각 변이 각각 한 유니언(union) 안에 있다고 가정하면 말이다. 간단한 서로소 집합 자료 구조인 랭크에 의한 합집합을 사용하는 디스조인트-셋 숲(disjoint-set forest with union by rank)를 쓰더라도, $O(E)$ 개의 동작이 $O(E\log V)$ 시간 안에 행해진다. 그러므로 총 시간 복잡도는 $O(E\log E)=O(E\log V)$가 된다.

변들이 이미 정렬되어 있거나 선형 시간(linear time, $O(E)$) 안에 정렬될 수 있다면(예를 들어 카운팅 정렬, 기수 정렬), 크러스컬 알고리즘은 좀 더 고도의 서로소 집합 자료 구조를 사용할 수 있다. 이때 동작 시간 복잡도는 $O(E\alpha (V))$가 되는데, 여기서 $\alpha$는 아주 느리게 증가하는 단일-값 아커만 함수의 역함수를 말한다.

예제

	우리가 풀어야 할 그래프이다. 변 옆에 있는 숫자는 변의 가중치를 가리킨다. 지금은 모든 변들이 색이 동일하다.
	AD 와 CE 가 가장 짧은(가중치가 가장 작은) 변이다. 아무거나 골라서 AD를 선택한다. AD의 색을 변경하였다.
	이제, CE가, 가중치가 5로서, 고리(loop)를 생성하지 않는 가장 짧은 변이다. CE의 색을 변경하였다.
	같은 방식으로 고르면 다음 변은 DF이다. 가중치는 6이다.
	다음으로 가장 짧은 변은 AB와 BE인데, 둘 다 길이 (= 가중치)가 7이다. 임의로AB를 골랐다. BD는 빨강색으로 변경하였는데, ABD를 연결시키면 루프를 이루기 때문이다.
	다음으로 가장 짧은 변은 BE로서 길이 7이다. 더 많은 변들이 빨강으로 변했다. BCE 루프를 생성하기 때문에 BC가 빨강색으로 변했으며, DEBA 루프를 생성하기 때문에 DE가 빨강색으로 변했고, FEBAD 고리를 생성하기 때문에 FE가 빨강색으로 변했다.
	끝내, EG가 연결되면서 알고리즘이 종료된다. 최소 비용 신장 부분 그래프가 완성되었다.

정확성 증명

$P$를 연결 가중 그래프라 하고, $Y$를 크러스컬 알고리즘을 사용하여 생성된 $P$의 부분 그래프라고 가정하자. $Y$는 순환을 가질 수 없다. 마지막 변이 하나 추가되어 순환을 생성한 것이라면, 그 마지막 변은 서로 다른 나무 사이에 존재할 수 없으며, 한 부분나무 속에 존재해야만 하기 때문이다. (순환을 만들려면 각 꼭짓점들이 한 부분나무 속에서 이미 이어져 있어야 한다. 알고리즘의 절차상 그러한 마지막 변을 만들 수 없다는 뜻이다.) $Y$는 비연결 그래프일 수 없다. $Y$ 내에 또다른 연결 성분이 있었다면, 알고리즘의 절차에 의해, 그 둘을 연결하는 변이 추가되었을 것이기 때문이다. 결론을 내리면, $Y$는 $P$의 신장 부분 그래프이다.

다음으로는 신장 부분 그래프 $Y$가 최소 신장 부분 그래프(minimum spanning tree)임을 보이겠다.

$Y_{1}$이 최소 신장 부분 그래프라고 가정하자. 만약 $Y=Y_{1}$이면 $Y$도 최소 신장 부분 그래프가 된다. 이게 사실이 아니라고 가정하자. $e$가 $Y$에는 있으나 $Y_{1}$에는 없는 변이라고 가정하자. $Y_{1}\cup {e}$는 순환을 가질 수밖에 없다. 신장 부분 그래프에 변을 하나 더하면 더 이상 신장 부분 그래프가 아니기 때문이다. 이 순환은 다른 하나의 변$f$를 가지는데, $f$는 $e$가 $Y$에 추가되는 알고리즘의 단계에서 고려 안 된 변일 수밖에 없다. 안 그랬다면 $e$는 같은 나무의 다른 가지(branch)들을 서로 연결했을 것이고, 서로 다른 나무들은 연결시키지 않았을 것이기 때문이다. 그러므로$Y_{2}=Y_{1}\cup {e}\setminus {f}$도 역시 신장 부분 그래프이다. 이 신장 부분 그래프의 총 가중치 합(total weight)은 $Y_{1}$의 총 가중치보다 작다. 그 까닭은 $w(e)\leq w(f)$이므로 알고리즘이 $f$를 방문하기 전에 $e$를 먼저 방문했기 때문일 것이다. 만약 가중치들이 같았다면, 우리는 $Y$에는 있으나 $Y_{1}$에는 없는 변 $e$를 생각할 수 있다. 만약 남아 있는 변이 없었다면, $Y$나 $Y_{1}$가 서로 다른 변들로 구성되어 있었더라도 $Y$의 총 가중치 합이 $Y_{1}$의 총 가중치 합과 같을 것이다. 이 때도 역시 $Y$는 최소 신장 부분 그래프가 된다. 만약 $Y_{2}$의 총 가중치 합이 $Y_{1}$의 총 가중치 합보다 작은 경우에는, $Y_{1}$이 최소 신장 부분 그래프가 아니라는 결론에 다다르게 된다. 이것은 $w(e)<w(f)$인 변 $e,f$가 있다는 처음의 가정에 위배되게 된다. 결론적으로, $Y$는 ($Y_{1}$과 변들도 같고, 가중치도 같은) 완전한 최소 신장 부분 그래프가 될 수밖에 없다.

크러스컬 알고리즘의 결과인 신장 부분 그래프 Y의 비용이 최소임을 보이는 다른 방법은 수학적 귀납법이다. 다음 명제가 참임을 수학적 귀납법으로 증명한다.

"만약 F가 크러스컬 알고리즘의 각 단계에서 나타나는 변의 집합 중의 하나라고 하면 F를 포함하는 최소 생성나무가 있다."

이 명제를 증명하면 결국 크러스컬 알고리즘의 마지막 단계에 나타나는 생성나무 Y를 포함하는 최소 생성나무가 있고 Y가 곧 최소 생성나무이다.

1. 알고리즘의 첫 단계, 즉, 변을 선택하지 않은 단계에서 F는 공집합이다. 이때, 크러스컬 알고리즘을 적용하는 그래프는 유한개의 점과 변을 가진다. 그러므로 생성나무를 유한개 가진다. 정확성 증명의 처음에 크러스컬 알고리즘의 결과로 Y가 생성나무임을 증명했으므로 그래프가 가지는 생성나무는 하나 이상의 유한개이다. 그러므로 최소 생성나무가 존재한다. 그러므로 공집합 F를 포함하는 최소 생성나무가 존재한다.
2. 크러스컬 알고리즘의 각 단계 중에 나타나는 변의 집합 F를 포함하는 최소 생성나무 T가 있다고 가정하자.
3. 알고리즘의 다음 단계에 추가하는 변을 e라 하면 다음 단계의 집합은 F에 e를 추가한 집합 $F\cup {e}$이다. $F\cup {e}$를 포함하는 최소 생성나무가 존재함을 보인다. e는 T의 변이거나 아니다. (1) e가 T의 한 변이면 $F\cup {e}$를 포함하는 최소 생성나무는 T이다. (2) e가 T의 변이 아니라고 하자. 그런데 T는 그래프의 모든 점을 가지는 생성나무이다. 그러므로 e는 T가 가진 두 점 A와 B를 양끝 점으로 한다. T는 나무이므로 A에서 B로의 경로 p가 있다. 그리고 p는 유일하다. 그러므로 T에 e를 추가하면 $T\cup {e}$ 안에 회로 C가 생긴다. 이때 $T\cup {e}$에서 회로는 C하나뿐이다. $F\cup {e}$는 크러스컬 알고리즘의 정의 때문에 회로를 가질 수 없다. 그러므로 회로 C를 가질 수 없다. 그러므로 F도 "회로 C에서 변 e가 모자란 경로 p 전체"를 가질 수 없다. 그러므로 F가 가지지 않은 "경로 p의 변 f"가 있다. f가 경로 p에 있으므로 회로 C에도 있다. 그런데 회로 C가 $T\cup {e}$에서 유일한 회로이므로 f를 $T\cup {e}$에서 빼면 다시 나무가 된다. $T\cup {e}-f$는 그래프상의 점은 모두 가지므로 생성나무가 된다. 이제 $T\cup {e}-f$의 비용이 최소생성나무 T의 비용 이하임을 보인다. 크러스컬 알고리즘은 매 단계에서 최소 가중치의 변을 추가한다. F는 e와 f를 가지지 않고 f의 가중치가 e 이상이기 때문에 F를 만든 단계 다음에 e를 추가한 것이다. 그러므로 $T\cup {e}-f$의 비용은 T의 비용 이하이다. 즉, $T\cup {e}-f$는 최소 생성나무이다. $T\cup {e}$는 $F\cup {e}$를 포함하지만 f는 F의 원소가 아니므로 $T\cup {e}-f$는 $F\cup {e}$를 포함한다. 그러므로 $F\cup {e}$를 포함하는 최소 생성나무 $T\cup {e}-f$가 존재한다.

크러스컬 알고리즘 다른 형태의 증명

나무에 관한 정리에서 n개의 꼭짓점을 가진 그래프가 연결 그래프일 때, 회로를 가지지 않는 것과 n-1개의 변을 가지는 것은 동일함이 알려져 있다. 알고리즘의 각 단계에서 얻는 그래프는 연결을 항상 유지하고 있으며 마지막 단계의 그래프는 n-1개의 변이 남으므로 회로를 가지지 않는다. 그러므로 알고리즘을 통해 얻은 그래프는 생성나무이다.

이제 남은 것은 결과로 얻은 생성나무가 최소 비용임을 보이는 것이다. 그러므로 다음과 같은 명제를 수학적 강귀납법으로 증명한다.

"알고리즘의 각 단계의 그래프는 최소비용 생성나무를 포함한다."

1. 알고리즘의 최초 단계의 그래프는 변을 제거하지 않았으므로 최소비용 생성나무를 당연히 포함한다.
2. 알고리즘의 처음부터 n개의 변이 남을 때까지 각 단계의 그래프가 모두 최소비용 생성나무를 포함한다고 가정한다.
3. 알고리즘의 마지막 단계로 n-1개의 변이 남은 그래프인 생성나무가 최소비용 생성나무를 포함함을 보임으로써 결과로 나온 생성나무가 최소비용임을 보인다. n개의 변이 남았을 때, 그래프를 F라 하고 F가 포함하는 최소비용 생성나무를 T라고 하자. 그리고 F에서 변 e를 제거하여 알고리즘이 끝난다고 하자. T가 나무이고 회로를 가지지 않으므로 n-1개의 변을 가진다. F에서 변 f를 제거하면 T가 된다고 하자. 알고리즘에서 최대 가중치를 가진 변을 제거하므로 e의 가중치는 f 이상이다. 그러므로 F-e는 T의 비용 이하의 생성나무이다. 그런데 T는 최소비용 생성나무이므로 F-e는 T와 비용이 같다. 즉 F-e는 최소비용 생성나무이고 자신을 포함한다.

의사 코드

 1  function Kruskal(G)
 2    for each vertex v in G do
 3      Define an elementary cluster C(v) ← {v}.
 4    Initialize a priority queue Q to contain all edges in G, using the weights as keys.
 5    Define a tree T ← Ø       //T will ultimately contain the edges of the MST
 6     // n is total number of vertices
 7    while T has fewer than n-1 edge

참고 문헌

• Joseph. B. Kruskal: On the Shortest Spanning Subtree of a Graph and the Traveling Salesman Problem. In: Proceedings of the American Mathematical Society, Vol 7, No. 1 (Feb, 1956), pp. 48–50
• Thomas H. Cormen, Charles E. Leiserson, 로널드 라이베스트, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Section 23.2: The algorithms of Kruskal and Prim, pp.567–574.
• Michael T. Goodrich and Roberto Tamassia. Data Structures and Algorithms in Java, Fourth Edition. John Wiley & Sons, Inc., 2006. ISBN 0-471-73884-0. Section 13.7.1: Kruskal's Algorithm, pp.632.

같이 보기

• 데이크스트라 알고리즘
• 프림 알고리즘
• 최소 비용 신장 트리

외부 링크

• (영어) 크러스컬 알고리즘을 애니메이션으로 보기(자바 플러그인이 필요함)
• (영어) 크러스컬 알고리즘과 프림 알고리즘을 이용하여 미로 문제를 생성하고 해결하기 컷-더-놋 제공.
• (영어) 미니멈 스패닝 트리 문제: 크러스컬 알고리즘