最小生成树(Prim算法)

 1 #define _CRT_SECURE_NO_WARNINGS
 2 /*
 3 7 10
 4 0 1 5
 5 0 2 2
 6 1 2 4
 7 1 3 2
 8 2 3 6
 9 2 4 10
10 3 5 1
11 4 5 3
12 4 6 5
13 5 6 9
14 */
15 #include <iostream>
16 #include <vector>
17 #include <algorithm>
18 using namespace std;
19 
20 const int maxn = 1010 + 10;
21 const int INF = 9999999;
22 int cost[maxn][maxn];       //cost[u][v]表示边e=(u,v)的权值(不存在时候设为INF)
23 int mincost[maxn];          //从集合X出发的边到每个顶点的最小权值
24 bool used[maxn];            //顶点i是否包含在集合X中
25 int V, E;                   //顶点数
26 void init();
27 void input();
28 int prim();
29 
30 int prim()
31 {
32     for (int i = 0; i < V; ++i) {
33         mincost[i] = INF;
34         used[i] = false;
35     }
36     mincost[0] = 0;
37     int res = 0;
38 
39     while (true) {
40         int v = -1;
41         //从不属于X的顶点中选取从X到其权值最小的顶点
42         for (int u = 0; u < V; u++) {
43             if (!used[u] && (v == -1 || mincost[u] < mincost[v]))
44                 v = u;
45         }
46 
47         if (v == -1) break;
48         used[v] = true;          //把顶点v加入到X
49         res += mincost[v];       //把长度加到结果里
50 
51         for (int u = 0; u < V; u++) {
52             //下一次到新节点u最短 = min(已知中最短(或者还未知)，尚未探索的最短).
53             mincost[u] = min(mincost[u], cost[v][u]);  
54         }
55     }
56     return res;
57 }
58 
59 void init()
60 {
61     for (int i = 0; i < V; i++) {
62         for (int j = 0; j < V; j++) {
63             if (i == j) {
64                 cost[i][j] = 0;
65             }
66             else {
67                 cost[i][j] = INF;
68             }
69         }
70 
71     }
72 }
73 
74 void input()
75 {
76     int s, t, ct;
77     for (int i = 0; i < E; i++) {
78         cin >> s >> t >> ct;
79         cost[s][t] = cost[t][s] = ct;
80     }
81 }
82 
83 int main()
84 {
85     cin >> V >> E;
86     init();
87     input();
88     int res = prim();
89     cout << res << endl;
90     return 0;
91 }