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

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

2024-07-10 21:13:19   217人阅读

2014.07.04 22:42

简介：

　　给定一个无向带权连通图（三个条件），选出n-1条边将这n个顶点连成一棵树，使得这棵树的权值之和最小。

描述：

　　本次使用Prim算法来解决这个问题。Prim算法的思想是两点：BFS与贪婪。

　　我们从一个顶点出发，把这个顶点对应的边加入到优先队列中。既然是优先队列，当然是边的权值短的优先。

　　每一轮我们从优先队列中取出一条边u->v，u已经被访问过（选出的这条边权值必然是目前最短的），如果v未被访问过，那么标记v，并把从v出发的边加入队列。

　　这样从一点出发逐渐散开的搜索形式属于广度优先搜索，而短边优先的策略则属于贪婪。因此Prim算法就是BFS与贪婪算法的结合。

　　说实话，直接看代码实现或许更简单。

实现：

  1 // My implementation for Prim‘s Algorithm, for minimum spanning tree problem.  2 #include <algorithm>  3 #include <iostream>  4 #include <vector>  5 #include <queue>  6 using namespace std;  7   8 const int INFINITY = 1000000000;  9  10 struct Edge { 11     int x; 12     int y; 13     int cost; 14     Edge(int _x = 0, int _y = 0, int _cost = 0): x(_x), y(_y), cost(_cost) {}; 15 }; 16  17 struct GreaterFunctor { 18     bool operator () (const Edge &e1, const Edge &e2) { 19         return e1.cost > e2.cost; 20     } 21 }; 22  23 int primsAlgorithm(const vector<vector<int> > &graph) 24 { 25     // Prim‘s Algorithm for weighted undirected graph. 26      27     int n; 28     n = (int)graph.size(); 29     if (n < 2) { 30         return 0; 31     } 32  33     int i; 34     // Minimal heap, the top is smallest. 35     priority_queue<Edge, vector<Edge>, GreaterFunctor> pq; 36     vector<bool> visited; 37     int visited_count; 38     int min_cost; 39      40     visited.resize(n, false); 41      42     // Start constructing the tree from 0th vertex. 43     min_cost = 0; 44     visited[0] = true; 45     for (i = 1; i < n; ++i) { 46         if (graph[0][i] == INFINITY) { 47             continue; 48         } 49         pq.push(Edge(0, i, graph[0][i])); 50     } 51     visited_count = n - 1; 52      53     Edge e; 54     while (!pq.empty()) { 55         e = pq.top(); 56         pq.pop(); 57         if (visited[e.y]) { 58             continue; 59         } 60         min_cost += e.cost; 61         visited[e.y] = true; 62         --visited_count; 63         if (visited_count == 0) { 64             break; 65         } 66          67         for (i = 0; i < n; ++i) { 68             if (i == e.y || graph[e.y][i] == INFINITY || visited[i]) { 69                 continue; 70             } 71             pq.push(Edge(e.y, i, graph[e.y][i])); 72         } 73     } 74      75     while (!pq.empty()) { 76         pq.pop(); 77     } 78      79     return min_cost; 80 } 81  82 int main() 83 { 84     vector<vector<int> > graph; 85     int n; 86     int nk; 87     int i, j; 88     int tmp, tmp_dist; 89     int min_cost; 90      91     while (cin >> n && n > 0) { 92         graph.resize(n); 93         for (i = 0; i < n; ++i) { 94             graph[i].resize(n, INFINITY); 95         } 96          97         for (i = 0; i < n; ++i) { 98             cin >> nk; 99             for (j = 0; j < nk; ++j) {100                 cin >> tmp >> tmp_dist;101                 graph[i][tmp] = graph[tmp][i] = tmp_dist;102             }103         }104         105         min_cost = primsAlgorithm(graph);106         107         cout << "The weighted sum of minimum spanning tree is " << min_cost << "." << endl;108         109         for (i = 0; i < n; ++i) {110             graph[i].clear();111         }112         graph.clear();113     }114     115     return 0;116 }

 


联系
我们