Greedy Method

크러스컬(Kruskal) 알고리즘이란? Kruskal's Algorithm은 최소 비용 신장 그래프를 찾는 알고리즘 입니다. 변의 개수를 E, 꼭지점의 개수를 V라고 한다면 Kruskal's Algorithm은 O(ElogV)의 시간 복잡도를 갖습니다. 크러스컬의 MST(욕심쟁이 방법) 알고리즘 간략 Code: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 edge_set kruskal_MST(edge_set E, int n) { sort(E); // 간선 정렬 edge_set MST_E = { }; for (i=0; i<n; i++) init_set(i); // n개의 집합(트리)을 생성 while(MST_E의 간선 수 < n - 1) { (u, v) = E의 최소 가중치 간선; E = E - {(u, v)}; if(find(u) != find(v)) // u와 v가 다른 집합(트리) 원소 { MST_E = MST_E ∪ {(u, v)}; // 간선 추가 union(u, v); // 두 집합(트리)을 합병 } } return MST_E; } - 예제 - ...