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

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

2024-07-10 21:08:19   223人阅读

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 }

 


联系
我们