《数据结构与算法分析：C语言描述》复习——第九章“图论”—

《数据结构与算法分析：C语言描述》复习——第九章“图论”——Kruskal算法

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 }