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

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 }

 

《数据结构与算法分析:C语言描述》复习——第九章“图论”——Prim算法,布布扣,bubuko.com

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

上一篇:【给你的产品加点料】中国移动数据语音与天猫精灵携手打造打造优质智能生活


下一篇:Hybrid APP之Native和H5页面交互