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 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 | #include <iostream> #include <algorithm> #include <vector> //C++ STL 사용 using namespace std; typedef pair<int, int> iPair; struct DisjointSets // Disjoint Sets은 집합을 트리로 형성하여 그래프의 Cycle을 형성하는지 체크. { int *parent, *rnk; int n; DisjointSets(int n) // 생성자 { this->n = n; parent = new int[n + 1]; rnk = new int[n + 1]; for (int i = 0; i <= n; i++) { rnk[i] = 0; parent[i] = i; } } int find(int u) // 같은 부모를 가지는 지 확인하는 함수 { if (u != parent[u]) parent[u] = find(parent[u]); return parent[u]; } void unionmerge(int x, int y) // 부모 노드를 병합 { x = find(x), y = find(y); if (rnk[x] > rnk[y]) // 더 작은 숫자를 부모에 병합 parent[y] = x; else // If rnk[x] <= rnk[y] parent[x] = y; if (rnk[x] == rnk[y]) rnk[y]++; } }; struct Graph { int V, E; vector< pair<int, iPair> > edges; Graph(int V, int E) // 생성자 { this->V = V; this->E = E; } void addEdge(int u, int v, int w) // init_set() 과 같은 함수, 정점을 추가한다. { edges.push_back({ w,{ u, v } }); } int kruskalMST(); }; int Graph::kruskalMST() { int mst_wt = 0; // 초기값은 0 sort(edges.begin(), edges.end()); // 오름차순 정렬 DisjointSets DS(V); vector< pair<int, iPair> >::iterator it; for (it = edges.begin(); it != edges.end(); it++) { int u = it->second.first; int v = it->second.second; int set_u = DS.find(u); int set_v = DS.find(v); // 동일한 부모를 가르키지 않는 경우, 즉 사이클이 발생하지 않을 때만 선택. if (set_u != set_v) { cout << u << " - " << v << endl; // 결과 값 출력 mst_wt += it->first; DS.unionmerge(set_u, set_v); //DisjointSets의 unionmerge 함수 } } return mst_wt; } int main() { int V = 9, E = 14; //정점, 간선의 수 Graph kruskal(V, E); // edge 추가 kruskal.addEdge(0, 1, 4); kruskal.addEdge(0, 7, 8); kruskal.addEdge(1, 2, 8); kruskal.addEdge(1, 7, 11); kruskal.addEdge(2, 3, 7); kruskal.addEdge(2, 5, 4); kruskal.addEdge(2, 8, 2); kruskal.addEdge(3, 4, 9); kruskal.addEdge(3, 5, 14); kruskal.addEdge(4, 5, 10); kruskal.addEdge(5, 6, 2); kruskal.addEdge(6, 7, 1); kruskal.addEdge(6, 8, 6); kruskal.addEdge(7, 8, 7); cout << "MST의 연결된 정점\n"; int mst_wt = kruskal.kruskalMST(); // cout << "\nMST 비용은 " << mst_wt << "입니다." << endl; return 0; } | cs |
'대학교 > 2.알고리즘' 카테고리의 다른 글
[차근차근 이해하는 알고리즘] 백트래킹 (0) | 2018.05.14 |
---|---|
[차근차근 이해하는 알고리즘] 동적 계획법 (0) | 2018.05.14 |
[차근차근 이해하는 알고리즘] 분할정복 (0) | 2018.05.14 |
[차근차근 이해하는 알고리즘]욕심쟁이 방법(Greed) (0) | 2018.05.14 |
[차근차근 이해하는 알고리즘]알고리즘 기초 (0) | 2018.05.14 |