最小生成树算法实际上就是一个不断添加safe edge，直到当前的最小生成树包含所有节点为止，如果算法停止时，还有没有访问的节点，说明该图是不连通的，返回-1。当算法运行完毕，最小生成树的边即为每个节点与p的边。
prim算法：
首先是数据结构的定义：
1 #include <queue> 2 #include <limits> 3 #include <map> 4 5 using namespace std; 6 7 struct Edge 8 { 9 int end; 10 int weight; 11 12 bool operator<(const Edge& other) const 13 { 14 return weight > other.weight; 15 } 16 }; 17 18 struct Node 19 { 20 string value; 21 vector<Edge> edges; 22 bool flag; 23 int p; 24 int mindist; 25 }; 26 27 struct Graph 28 { 29 std::vector<Node> nodes; 30 std::map<std::string, int> nodemap; 31 }
由于需要使用优先队列找出safe edge（即与当前树距离最近的节点），所以对Edge结构还定义了一个小于操作符。
然后就是prim算法：
1 int MST_prim(Graph& g) 2 { 3 for (size_t i = 0; i < g.nodes.size(); ++i) 4 { 5 g.nodes[i].flag = false; 6 g.nodes[i].p = -1; 7 g.nodes[i].mindist = numeric_limits<int>::max(); 8 } 9 priority_queue<Edge> pq; 10 Edge e_init = { 0, 0 }; 11 pq.push(e_init); 12 13 int sum = 0; 14 while (!pq.empty()) 15 { 16 Edge e; 17 do 18 { 19 e = pq.top(); pq.pop(); 20 } while (g.nodes[e.end].flag == true && !pq.empty()); 21 if (g.nodes[e.end].flag == true) 22 break; 23 sum += e.weight; 24 g.nodes[e.end].flag = true; 25 g.nodes[e.end].mindist = 0; 26 for (size_t i = 0; i < g.nodes[e.end].edges.size(); ++i) 27 { 28 Edge ev = g.nodes[e.end].edges[i]; 29 if (ev.weight < g.nodes[ev.end].mindist) 30 { 31 g.nodes[ev.end].mindist = ev.weight; 32 g.nodes[ev.end].p = e.end; 33 pq.push(ev); 34 } 35 } 36 } 37 38 for (size_t i = 0; i < g.nodes.size(); ++i) 39 { 40 if (g.nodes[i].flag == false) 41 return -1; 42 } 43 return sum; 44 }
算法最后检查还有没有没访问到的节点，如果有，说明图是不连通的，直接返回-1。
另外一个就是Kruskal算法，该算法适合稀疏图，由于有大量的检查两个节点是否相连通，因此用并查集比较合适。算法代码如下（比较粗糙，没写成体系，作为测试而已）：
1 #include <iostream> 2 #include <vector> 3 #include <string> 4 #include <algorithm> 5 6 using namespace std; 7 8 struct Edge 9 { 10 int begin; 11 int end; 12 int weight; 13 bool operator<(const Edge& other) const 14 { 15 return weight < other.weight; 16 } 17 }; 18 19 struct Node 20 { 21 int p; 22 int order; 23 }; 24 25 vector<Node> nodes; 26 vector<Edge> edges; 27 vector<Edge> min_span_edges; 28 int num_nodes; 29 30 void make_sets(int num_nodes) 31 { 32 for (int i = 0; i < num_nodes; ++i) 33 { 34 Node n = { i, 0 }; 35 nodes.push_back(n); 36 } 37 } 38 39 int find_set(int x) 40 { 41 if (x != nodes[x].p) 42 { 43 nodes[x].p = find_set(nodes[x].p); 44 } 45 return nodes[x].p; 46 } 47 48 void join(int x, int y) 49 { 50 int m = find_set(x); 51 int n = find_set(y); 52 if (nodes[m].order > nodes[n].order) 53 { 54 nodes[n].p = m; 55 } 56 else 57 { 58 nodes[m].p = n; 59 if (nodes[m].order == nodes[n].order) 60 { 61 nodes[n].order++; 62 } 63 } 64 } 65 66 void input_edges() 67 { 68 cout << "please firstly input the num of nodes : "; 69 cin >> num_nodes; 70 cout << "please input the edges by format: node_num1 node_num2 edge_weight." << endl; 71 while (1) 72 { 73 Edge e; 74 cin >> e.begin >> e.end >> e.weight; 75 if (e.weight == -1) 76 break; 77 edges.push_back(e); 78 } 79 } 80 81 int kruskal() 82 { 83 int sum_span = 0; 84 make_sets(num_nodes); 85 sort(edges.begin(), edges.end()); 86 for (size_t i = 0; i < edges.size(); ++i) 87 { 88 if (find_set(edges[i].begin) != find_set(edges[i].end)) 89 { 90 min_span_edges.push_back(edges[i]); 91 sum_span += edges[i].weight; 92 join(edges[i].begin, edges[i].end); 93 } 94 } 95 return sum_span; 96 } 97 98 void main() 99 { 100 input_edges(); 101 int span_weight = kruskal(); 102 cout << span_weight; 103 cout << endl; 104 for (size_t i = 0; i < min_span_edges.size(); ++i) 105 { 106 cout << min_span_edges[i].begin << "," << min_span_edges[i].end << endl; 107 } 108 }