크루스칼 알고리즘(Kruskal Algorithm)

크루스칼 알고리즘(Kruskal Algorithm)

크루스칼 알고리즘(Kruskal Algorithm)

크루스칼 알고리즘 : MST(최소 신장 트리)을 찾는 알고리즘

시간 복잡도 : 변의 개수 E, 꼭지점의 개수 V라고 할 때, O(ElogV)

크루스칼 알고리즘 개요 :

- 크루스칼 알고리즘은 그리디 기법(탐욕 기법)을 기반.

(1) 주어진 그래프의 모든 간선에 대해, 간선의 연결비용을 오름차순 정렬.

(2) 정렬된 간선들을 순서대로 선택하여, 간선의 양 끝을 Union을 함. (선택된 두 정점이 같은 집합에 속해있다면 cycle이 있다고 판단하여 pass함)

(3) 이를 V-1개의 간선을 선택할 때 까지 반복합니다.

Start 1 3 4 1 2 2 5 2 5 6 4 Des 4 5 6 2 5 3 6 4 7 7 5 Cost 5 5 6 7 7 8 8 9 9 11 15

위의 그래프에서 초기 간선들을 모두 비용 순으로 정렬하면 위와 같은 표의 상태가 될 것이다.

또한, 모든 노드의 루트 노드는 최초의 상태이므로 아래와 같은 상태가 될 것이다.

Node 1 2 3 4 5 6 7 Root 1 2 3 4 5 6 7

이제 정렬된 간선 리스트 중 간선을 순서대로 뽑아서 사이클이 존재하지 않는다면 선택, 존재한다면 패쓰를 하며 모든 간선을 탐색합니다.

Start 1 3 4 1 2 2 5 2 5 6 4 Des 4 5 6 2 5 3 6 4 7 7 5 Cost 5 5 6 7 7 8 8 9 9 11 15

위와 같이 가장 Cost가 작은 1->4 간선이 선택된다.

Node 1 2 3 4 5 6 7 Root 1 2 3 1 5 6 7

1과 4는 Union이 되므로 루트 노드가 저장된 리스트에서 4는 루트가 1로 갱신된다.

Start 1 3 4 1 2 2 5 2 5 6 4 Des 4 5 6 2 5 3 6 4 7 7 5 Cost 5 5 6 7 7 8 8 9 9 11 15

그 다음은 Cost가 이전과 같은 3->5 간선이 선택된다.

Node 1 2 3 4 5 6 7 Root 1 2 3 1 3 6 7

첫 번째와 같이 5의 루트 노드는 3으로 갱신된다.

Start 1 3 4 1 2 2 5 2 5 6 4 Des 4 5 6 2 5 3 6 4 7 7 5 Cost 5 5 6 7 7 8 8 9 9 11 15

위와 같이 다음으로 Cost가 작은 4->6 간선이 선택된다.

Node 1 2 3 4 5 6 7 Root 1 2 3 1 3 1 7

위와 같이 6의 루트 노드가 4로 갱신된다.

Start 1 3 4 1 2 2 5 2 5 6 4 Des 4 5 6 2 5 3 6 4 7 7 5 Cost 5 5 6 7 7 8 8 9 9 11 15

위와 같이 다음으로 Cost가 작은 1->2 간선이 선택된다.

Node 1 2 3 4 5 6 7 Root 1 1 3 1 3 1 7

위와 같이 2의 루트 노드가 1로 갱신된다.

Start 1 3 4 1 2 2 5 2 5 6 4 Des 4 5 6 2 5 3 6 4 7 7 5 Cost 5 5 6 7 7 8 8 9 9 11 15

위와 같이 다음으로 Cost가 작은 2->5 간선이 선택된다.

Node 1 2 3 4 5 6 7 Root 1 1 1 1 1 1 7

위와 같이 5의 루트 노드가 2로 갱신된다. 이 때, 3의 루트도 갱신된다.

Start 1 3 4 1 2 2 5 2 5 6 4 Des 4 5 6 2 5 3 6 4 7 7 5 Cost 5 5 6 7 7 8 8 9 9 11 15

위와 같이 다음으로 Cost가 작은 2->3 간선이 선택된다. 하지만 이 때, 싸이클을 이루는 것을 볼 수 있다. 따라서 이는 선택이 될 수 없으므로 pass를 하고 다음 간선을 확인한다.

Node 1 2 3 4 5 6 7 Root 1 1 1 1 1 1 7

Start 1 3 4 1 2 2 5 2 5 6 4 Des 4 5 6 2 5 3 6 4 7 7 5 Cost 5 5 6 7 7 8 8 9 9 11 15

위와 같이 다음으로 Cost가 작은 5->6 간선이 선택된다. 하지만 이 때도, 싸이클을 이루는 것을 볼 수 있다. 따라서 이는 선택이 될 수 없으므로 pass를 하고 다음 간선을 확인한다.

Node 1 2 3 4 5 6 7 Root 1 1 1 1 1 1 7

Start 1 3 4 1 2 2 5 2 5 6 4 Des 4 5 6 2 5 3 6 4 7 7 5 Cost 5 5 6 7 7 8 8 9 9 11 15

위와 같이 다음으로 Cost가 작은 2->4 간선이 선택되지만 이도 싸이클을 이루므로 다음 간선을 선택한다. 5->7 간선은 싸이클을 이루지 않으므로 선택됨을 볼 수 있다.

Node 1 2 3 4 5 6 7 Root 1 1 1 1 1 1 1

Start 1 3 4 1 2 2 5 2 5 6 4 Des 4 5 6 2 5 3 6 4 7 7 5 Cost 5 5 6 7 7 8 8 9 9 11 15

V-1개(6개)의 간선을 확인했으므로 MST가 완성되었다.

Node 1 2 3 4 5 6 7 Root 1 1 1 1 1 1 1

완성된 MST의 모습은 아래위 같다.

크루스칼 알고리즘은 Disjoint set의 성질을 이용하여 구현하므로 어렵지 않게 구현이 가능하다. 다음 포스트에서는 간단하게 구현과 예제를 다루어 보도록 하겠습니다.

from http://dabonee.tistory.com/39 by ccl(A) rewrite - 2021-09-25 19:59:58