2014.07.04 23:03
简介：
给定一个无向带权连通图（三个条件），选出n-1条边将这n个顶点连成一棵树，使得这棵树的权值之和最小。
描述：
本次使用Kruskal算法来解决这个问题。
如果有n个顶点的话，我们需要n-1条边来拼成一棵树。
Kruskal算法的基本思路，是每次拼上一条边，看看是否会造成一个环，如果会形成环则放弃这条边。
怎么保证拼成的那棵树权值最小呢？把所有边按权值由小到大排序。从小到大一个个试就可以了。
怎么确定加入一条边后是否会形成环呢？用并查集。对于一条无向图的边u-v，如果并查集中u和v对应的根节点相同，代表u、v已经连通了，这时再加入u-v就会形成一个环。
Kruskal算法可以说是学完并查集之后的第一个应用了。
由于需要对所有边进行排序，所以Kruskal算法的效率对于密集图（和恐惧症无关）肯定不那么好。
实现：
1 // My implementation for Prim‘s Algorithm, for minimum spanning tree problem. 2 #include <algorithm> 3 #include <iostream> 4 #include <vector> 5 using namespace std; 6 7 const int INFINITY = 1000000000; 8 9 struct Edge { 10 int x; 11 int y; 12 int cost; 13 Edge(int _x = 0, int _y = 0, int _cost = 0): x(_x), y(_y), cost(_cost) {}; 14 }; 15 16 bool comparator(const Edge &e1, const Edge &e2) { 17 return e1.cost < e2.cost; 18 } 19 20 int findRoot(vector<int> &dj, int x) 21 { 22 int r, k; 23 24 r = x; 25 while (r != dj[r]) { 26 r = dj[r]; 27 } 28 29 // Path compression speeds up the disjoint set. 30 k = x; 31 while (x != r) { 32 x = dj[x]; 33 dj[k] = r; 34 k = x; 35 } 36 37 return r; 38 } 39 40 int kruskalsAlgorithm(const vector<vector<int> > &graph) 41 { 42 // Kruskal‘s Algorithm for weighted undirected graph. 43 int n; 44 n = (int)graph.size(); 45 if (n < 2) { 46 return 0; 47 } 48 49 // Disjoint set 50 vector<int> dj; 51 vector<Edge> edges; 52 int rx, ry; 53 int i, j; 54 55 for (i = 0; i < n; ++i) { 56 for (j = i + 1; j < n; ++j) { 57 if (graph[i][j] == INFINITY) { 58 continue; 59 } 60 edges.push_back(Edge(i, j, graph[i][j])); 61 } 62 } 63 sort(edges.begin(), edges.end(), comparator); 64 65 dj.resize(n); 66 for (i = 0; i < n; ++i) { 67 dj[i] = i; 68 } 69 70 int edge_count = n - 1; 71 int min_cost = 0; 72 int ec = (int)edges.size(); 73 for (i = 0; i < ec; ++i) { 74 rx = findRoot(dj, edges[i].x); 75 ry = findRoot(dj, edges[i].y); 76 if (rx == ry) { 77 continue; 78 } 79 dj[rx] = ry; 80 findRoot(dj, edges[i].x); 81 82 min_cost += edges[i].cost; 83 --edge_count; 84 if (edge_count == 0) { 85 break; 86 } 87 } 88 edges.clear(); 89 90 return min_cost; 91 } 92 93 int main() 94 { 95 vector<vector<int> > graph; 96 int n; 97 int nk; 98 int i, j; 99 int tmp, tmp_dist; 100 int min_cost; 101 102 while (cin >> n && n > 0) { 103 graph.resize(n); 104 for (i = 0; i < n; ++i) { 105 graph[i].resize(n, INFINITY); 106 } 107 108 for (i = 0; i < n; ++i) { 109 cin >> nk; 110 for (j = 0; j < nk; ++j) { 111 cin >> tmp >> tmp_dist; 112 graph[i][tmp] = graph[tmp][i] = tmp_dist; 113 } 114 } 115 116 min_cost = kruskalsAlgorithm(graph); 117 118 cout << "The weighted sum of minimum spanning tree is " << min_cost << "." << endl; 119 120 for (i = 0; i < n; ++i) { 121 graph[i].clear(); 122 } 123 graph.clear(); 124 } 125 126 return 0; 127 }