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 }