크러스컬 알고리즘

컴퓨터 과학에서 크러스컬 알고리즘()은 최소 비용 신장 부분 트리를 찾는 알고리즘이다. 변의 개수를 formula_1, 꼭짓점의 개수를 formula_2라고 하면 이 알고리즘은 formula_3의 시간복잡도를 가진다.
개요.
크러스컬 알고리즘은 아래의 순서대로 작동한다.
알고리즘이 종료됐을 때 숲 "F"는 하나의 최소 비용 신장 부분 그래프만을 가지게 된다.
크러스컬 알고리즘의 다른 형태가 있다. 이것은 그래프에서 변을 제거하는 방식이다.
알고리즘.
formula_1를 변의 개수라 하고, formula_2를 꼭짓점의 개수라고 하자. 크러스컬 알고리즘은 formula_3 시간 안에 동작한다고 증명될 수 있다. 간단한 자료 구조가 쓰인다면 formula_7 안에 동작한다. 이 동작 시간은 동일한데, 그 까닭은 다음과 같다:
이러한 시간 복잡도 한계는 다음과 같은 방법으로 도달할 수 있다. 변들을 그 가중치 순으로 formula_15 시간 내에 정렬한다. 정렬을 함으로써, "집합 S로부터 최소 가중치를 갖는 변을 제거한다"는 동작이 상수 시간에 행해질 수 있게 된다. 서로소 집합 자료 구조(유니온 파인드: 결합과 검색)를 이용하여 어떤 꼭짓점이 어떤 콤포넌트(component)에 속하는 지 추적한다. 디스조인트-셋 찾기(find) 동작 두 번에 formula_16 시간이 걸린다. 각 변이 각각 한 유니언(union) 안에 있다고 가정하면 말이다. 간단한 서로소 집합 자료 구조인 랭크에 의한 합집합을 사용하는 디스조인트-셋 숲(disjoint-set forest with union by rank)를 쓰더라도, formula_16 개의 동작이 formula_7 시간 안에 행해진다. 그러므로 총 시간 복잡도는 formula_19가 된다.
변들이 이미 정렬되어 있거나 선형 시간(linear time, formula_16) 안에 정렬될 수 있다면(예를 들어 카운팅 정렬, 기수 정렬), 크러스컬 알고리즘은 좀 더 고도의 서로소 집합 자료 구조를 사용할 수 있다. 이때 동작 시간 복잡도는 formula_21가 되는데, 여기서 formula_22는 아주 느리게 증가하는 단일-값 아커만 함수의 역함수를 말한다.
정확성 증명.
formula_23를 연결 가중 그래프라 하고, formula_24를 크러스컬 알고리즘을 사용하여 생성된 formula_23의 부분 그래프라고 가정하자. formula_24는 순환을 가질 수 없다. 마지막 변이 하나 추가되어 순환을 생성한 것이라면, 그 마지막 변은 서로 다른 나무 사이에 존재할 수 없으며, 한 부분나무 속에 존재해야만 하기 때문이다. (순환을 만들려면 각 꼭짓점들이 한 부분나무 속에서 이미 이어져 있어야 한다. 알고리즘의 절차상 그러한 마지막 변을 만들 수 없다는 뜻이다.) formula_24는 비연결 그래프일 수 없다. formula_24 내에 또다른 연결 성분이 있었다면, 알고리즘의 절차에 의해, 그 둘을 연결하는 변이 추가되었을 것이기 때문이다. 결론을 내리면, formula_24는 formula_23의 신장 부분 그래프이다.
다음으로는 신장 부분 그래프 formula_24가 최소 신장 부분 그래프(minimum spanning tree)임을 보이겠다.
formula_32이 최소 신장 부분 그래프라고 가정하자. 만약 formula_33이면 formula_24도 최소 신장 부분 그래프가 된다. 이게 사실이 아니라고 가정하자. formula_35가 formula_24에는 있으나 formula_32에는 없는 변이라고 가정하자. formula_38는 순환을 가질 수밖에 없다. 신장 부분 그래프에 변을 하나 더하면 더 이상 신장 부분 그래프가 아니기 때문이다. 이 순환은 다른 하나의 변formula_39를 가지는데, formula_39는 formula_35가 formula_24에 추가되는 알고리즘의 단계에서 고려 안 된 변일 수밖에 없다. 안 그랬다면 formula_35는 같은 나무의 다른 가지(branch)들을 서로 연결했을 것이고, 서로 다른 나무들은 연결시키지 않았을 것이기 때문이다. 그러므로formula_44도 역시 신장 부분 그래프이다. 이 신장 부분 그래프의 총 가중치 합(total weight)은 formula_32의 총 가중치보다 작다. 그 까닭은 formula_46이므로 알고리즘이 formula_39를 방문하기 전에 formula_35를 먼저 방문했기 때문일 것이다. 만약 가중치들이 같았다면, 우리는 formula_24에는 있으나 formula_32에는 없는 변 formula_35를 생각할 수 있다. 만약 남아 있는 변이 없었다면, formula_24나 formula_32가 서로 다른 변들로 구성되어 있었더라도 formula_24의 총 가중치 합이 formula_32의 총 가중치 합과 같을 것이다. 이 때도 역시 formula_24는 최소 신장 부분 그래프가 된다. 만약 formula_57의 총 가중치 합이 formula_32의 총 가중치 합보다 작은 경우에는, formula_32이 최소 신장 부분 그래프가 아니라는 결론에 다다르게 된다. 이것은 formula_60인 변 formula_61가 있다는 처음의 가정에 위배되게 된다. 결론적으로, formula_24는 (formula_32과 변들도 같고, 가중치도 같은) 완전한 최소 신장 부분 그래프가 될 수밖에 없다.
크러스컬 알고리즘의 결과인 신장 부분 그래프 Y의 비용이 최소임을 보이는 다른 방법은 수학적 귀납법이다. 다음 명제가 참임을 수학적 귀납법으로 증명한다.
"만약 F가 크러스컬 알고리즘의 각 단계에서 나타나는 변의 집합 중의 하나라고 하면 F를 포함하는 최소 생성나무가 있다."
이 명제를 증명하면 결국 크러스컬 알고리즘의 마지막 단계에 나타나는 생성나무 Y를 포함하는 최소 생성나무가 있고 Y가 곧 최소 생성나무이다.
크러스컬 알고리즘 다른 형태의 증명
나무에 관한 정리에서 n개의 꼭짓점을 가진 그래프가 연결 그래프일 때, 회로를 가지지 않는 것과 n-1개의 변을 가지는 것은 동일함이 알려져 있다. 알고리즘의 각 단계에서 얻는 그래프는 연결을 항상 유지하고 있으며 마지막 단계의 그래프는 n-1개의 변이 남으므로 회로를 가지지 않는다. 그러므로 알고리즘을 통해 얻은 그래프는 생성나무이다.
이제 남은 것은 결과로 얻은 생성나무가 최소 비용임을 보이는 것이다. 그러므로 다음과 같은 명제를 수학적 강귀납법으로 증명한다.
"알고리즘의 각 단계의 그래프는 최소비용 생성나무를 포함한다."
의사 코드.
 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