알고리즘 - 크루스칼

- Kruskal

- 탐욕적인 방법(greedy method), 간선 선택 기반  

- 간선들을 가중치의 오름차순으로 정렬, 사이클을 형성하지 않는 간선을 찾아서 현재의 최소 비용 신장 트리의 집합에 추가

- 시간복잡도 

- union-find 연산 (사이클, 집합)

  

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41

#define MAX_VERTECS 100   int parent[MAX_VERTECS]; // 부모 노드 int num[MAX_VERTECS]; // 각 집합의 크기   // 초기화 void set_init(int n) {     int i;     for(i=0; i<n; i++) {         parent[i] = -1;         num[i] = 1;       } }   // vertext가 속하는 집합을 반환한다. int set_find(int vertex) {     int p, s, i = -1;     for(i = vertex; (p=parent[i])>=0; i=p) // 루트 노드까지 반복         ;     s = i; // 집합의 대표 원소(최상위 부모노드)     for(i = vertex; (p=parent[i])>=0; i=p)         parent[i] = s; // 집합의 모든 원소들의 부모를 s로 설정     return s; }   // 두 개의 원소가 속한 집합을 합친다. void set_union(int s1, int s2) {     // 연산량을 줄이기 위해 정점의 개수가 적은 트리의 루트가 큰 트리의 루트를 가리키도록 함     if(num[s1] < num[s2]) {         parent[s1] = s2;         num[s2] += num[s1];     }     else {         parent[s2] = s1;         num[s1] += num[s2];     } }