최소 스패닝 트리와 크루스칼 알고리즘

크루스칼 알고리즘

---

크루스칼 알고리즘은 최소 스패닝 트리를 구현하는 알고리즘 중 한 가지 방법이다. 크루스칼 알고리즘은 간선의 가중치를 확인해서 그리디하게 간선을 선택해서 최소 스패닝 트리를 구현한다. 간선의 가중치를 오름차순으로 정렬해 간선을 하나씩 추가하는 방법, 내림차순으로 정렬해 필요없는 간선을 하나씩 제거하는 방법도 있다.

그리디한 방법은 순간의 최적해를 찾을 수는 있지만, 크게 봤을 때 정해가 되는지는 증명이 필요하다. 크루스칼 알고리즘은 이미 저명한 학자들에 의해서 그 타당성을 인정 받았기 때문에 받아들이기만 하면 된다고 한다. 

간선의 가중치를 오름차순으로 정렬해 필요한 간선을 하나씩 추가하는 방법은 다음과 같다. 

1. 간선의 가중치를 기준으로 정렬한다. (퀵정렬, 병합정렬 사용)
2. 가중치가 낮은 간선부터 사이클이 생기지 않는다면, 간선을 활용해 정점을 연결해준다.
3. "간선의 개수 = 정점의 개수 - 1"이 되면 탐색을 종료한다.

아래 그래프를 예로 들어, 크루스칼 알고리즘으로 최소 신장 트리를 완성하는 과정을 설명한다. 

노드	A	B	C	D	E	F
루트 노드	A	B	B	D	E	F

왼쪽 그래프는 시작 그래프다. 간선의 가중치가 가장 낮은 2를 선택해서 B,C를 연결해준다. 이 때의 Union Find 배열은 위의 표로 정리했다.

노드	A	B	C	D	E	F
루트 노드	A	B	B	B	B	B

왼쪽 그림에서는 간선의 가중치가 그 다음으로 낮은 3과 4를 활용해 D-E, D-F를 연결해준다. 이 때, B-C와 F-D-E는 다른 집합이기 때문에 다른 색으로 노드를 표시했다. 오른쪽 그림에서 간선의 가중치가 낮은 6을 활용해 D-C를 연결해주었다. 이제 D-C는 같은 그룹이 되었으므로, 주황색 노드로 공통으로 표시했다.

노드	A	B	C	D	E	F
루트 노드	A	B	B	B	B	B

그 다음으로 낮은 간선 가중치 7을 활용해 C-E를 연결하려 했는데, 이미 C와 E는 같은 그룹이었다. 위의 Union Find 표에서 확인할 수 있듯이 C와 E의 부모 노드는 B로 동일하기 때문이다. 이 때, 가중치 7 간선을 추가하게 되면 C-D-E-C의 사이클이 생기기 때문에 신장 트리의 정의에서 벗어난다. 따라서 7은 연결해주지 않고, 간선 가중치 8을 활용해 A와 D를 연결해준다.

이 때, 연결된 노드의 갯수는 6개, 사용된 간선의 갯수는 5개로 신장 트리를 구성하는 조건인 간선 개수 = 노드 개수 - 1을 만족하기 때문에 최소 신장 트리가 완전히 구성된 것을 확인할 수 있다. 완성된 최소 신장 트리의 모습은 위와 같다. 

 

크루스칼 알고리즘의 성능

---

먼저 간선을 정렬하는데 최소 O(ElogE)의 시간 복잡도가 필요하다. 그 후, 최악의 경우 E개의 간선에 대해서 Union Find로 사이클을 확인하기 때문에 O(1) * O(E)를 하기 때문에 O(E)의 시간 복잡도가 필요하다. 시간 복잡도는 O(ElogE + E)가 되며, 최종 시간복잡도는 O(ElogE)가 된다.

 

크루스칼 알고리즘의 구현

---

추가 업데이트 예정