最小生成树（prim算法实现）

 1 // C++ program to implement Prim's Algorithm
 2 #include <iostream>
 3 #include <queue>
 4 #include <vector>
 5 
 6 using PII = std::pair<int, int>;
 7 
 8 int prim(int x, const std::vector<std::vector<PII> >& graph) {
 9     // priority queue to maintain edges with respect to weights
10     std::priority_queue<PII, std::vector<PII>, std::greater<PII> > Q;
11 
12     //标记每个节点是否被访问
13     std::vector<bool> marked(graph.size(), false);
14     int minimum_cost = 0;
15 
16     Q.push(std::make_pair(0, x));
17     while (!Q.empty()) {
18         // Select the edge with minimum weight
19         PII p = Q.top();
20         Q.pop();
21         x = p.second;
22         // Checking for cycle
23         if (marked[x] == true) {
24             continue;
25         }
26         minimum_cost += p.first;
27         marked[x] = true;
28         for (const PII& neighbor : graph[x]) {
29             int y = neighbor.second;
30             if (marked[y] == false) {
31                 Q.push(neighbor);
32             }
33         }
34     }
35     return minimum_cost;
36 }
37 
38 int main() {
39     int nodes = 0, edges = 0;
40     std::cin >> nodes >> edges;  // number of nodes & edges in graph
41     if (nodes == 0 || edges == 0) {
42         return 0;
43     }
44 
45     std::vector<std::vector<PII> > graph(nodes);
46 
47     // Edges with their nodes & weight
48     for (int i = 0; i < edges; ++i) {
49         int x = 0, y = 0, weight = 0;
50         std::cin >> x >> y >> weight;
51         graph[x].push_back(std::make_pair(weight, y));
52         graph[y].push_back(std::make_pair(weight, x));
53     }
54 
55     // Selecting 1 as the starting node
56     int minimum_cost = prim(1, graph);
57     std::cout << minimum_cost << std::endl;
58     return 0;
59 }