크루스칼 Kruskal's algorithm

최소 신장 트리(MST) 를 만드는 방법중 하나입니다.
모든 정점을 연결하는 간선들의 가중치 합의 최소가 되는 트리입니다.

아래 gif animation도 있습니다.
https://upload.wikimedia.org/wikipedia/commons/thumb/5/5c/MST_kruskal_en.gif/200px-MST_kruskal_en.gif

순서는 아래와 같습니다.
1. 모든 간선을 가중치에 따라 오름차순으로 정렬을 합니다.
2. 가중치가 낮은 간선부터 선택하면서 트리를 만듭니다. 만약 사이클이 존재하면 다음 가중치가 낮은 간선을 선택합니다.
3. N개의 정점이 있다고 가정할때 N-1개의 간선이 선택될때까지 2를 반복합니다.
(정점의 갯수는 간선-1 이기 때문입니다.)

Wiki의 예로 설명하도록 하겠습니다.
https://en.wikipedia.org/wiki/Kruskal%27s_algorithm

가중치를 나열해 보았습니다.
A-B 7
A-D 5
B-C 8
B-D 9
B-E 7
C-E 5
D-E 15
D-F 6
E-F 8
E-G 9

오름차순으로 정렬합니다.
A-D 5
C-E 5
D-F 6
A-B 7
B-E 7
B-C 8
E-F 8
B-D 9
E-G 9
D-E 15

하나씩 선택합니다. 사이클이 되는것은 선택하지 않습니다.

A-D 5 선택

 C-E 5 선택

D-F 6 선택

 A-B 7 선택

 B-E 7 선택

B-C 8 미선택

E-F 8 미선택

B-D 9 미선택

E-G 9 선택

 D-E 15 미선택

전체적인 내용은 Prim보다는 이해하기가 쉽습니다.

Pseudocode

The following code is implemented with disjoint-set data structure:

KRUSKAL(G):
1 A = ∅
2 foreach v ∈ G.V:
3    MAKE-SET(v)
4 foreach (u, v) ordered by weight(u, v), increasing:
5    if FIND-SET(u) ≠ FIND-SET(v):
6       A = A ∪ {(u, v)}
7       UNION(u, v)
8 return A

하지만 구현적인 측면에서는 사이클검사가 어렵습니다. Pseudocode에서는 Find-set의 값같은지 구현을 직접 해야 합니다.
참고

C, pasted just now:  #include <stdio.h> #define COUNTW 10 int N = 7; int data[]={'A','B','C','D','E','F','G'}; int weight[COUNTW][3]={ {'A','B',7}, {'A','D',5}, {'B','C',8}, {'B','D',9}, {'B','E',7}, {'C','E',5}, {'D','E',15}, {'D','F',6}, {'E','F',8}, {'E','G',9} }; int parent[10]; int make_set(int x) { x = x-'A'; parent[x]=x; return 0; } int find_set(int x) { x = x-'A'; if(x == parent[x]) return x; return find_set(parent[x]+'A'); } int union_set(int x,int y) { parent[find_set(y)] = find_set(x); return 0; } int main() { int i,j; int temp[3]; int selected = 0; for(i=0;i<N;i++){ make_set(data[i]); } // sort for(i=0;i<COUNTW;i++){ for(j=i+1;j<COUNTW;j++){ if(weight[i][2]>weight[j][2]){ //swap temp[0] = weight[i][0]; temp[1] = weight[i][1]; temp[2] = weight[i][2]; weight[i][0] = weight[j][0]; weight[i][1] = weight[j][1]; weight[i][2] = weight[j][2]; weight[j][0] = temp[0]; weight[j][1] = temp[1]; weight[j][2] = temp[2]; } } } // print for(i=0;i<COUNTW;i++){ printf("%c-%c %d\n",weight[i][0],weight[i][1],weight[i][2]); } printf("sorted\n"); // select for(i=0;i<COUNTW;i++){ if(find_set(weight[i][0])!=find_set(weight[i][1])){ union_set(weight[i][0],weight[i][1]); printf("%c-%c %d\n",weight[i][0],weight[i][1],weight[i][2]); if(++selected >= N-1) break; } } return 0; } Output: A-D 5 C-E 5 D-F 6 A-B 7 B-E 7 B-C 8 E-F 8 B-D 9 E-G 9 D-E 15 sorted A-D 5 C-E 5 D-F 6 A-B 7 B-E 7 E-G 9