Idea: first, use vertex 0 to build the minimum spanning tree. At this time, the spanning tree has one vertex 0, and the weight from the tree to other vertices is 0 to each point. Then loop: find the minimum value of lowcost [] and include its corresponding vertices into the minimum spanning tree. Set as vertex a, and then judge whether the weight of a to other vertices is less than the corresponding value in lowcost []. If it is less than, update the value of lowcost [] (that is, the minimum weight from the minimum spanning tree to other vertices at this time), and then enter the next cycle.

1. Establish adjvex [] to store the vertices included in the minimum spanning tree, and establish lowcost [] to store the weights of edges.

2. From vertex 0, lowcost[i] is set to arc[0][i].

3. Initialization is completed and the cycle begins. From 1, the value of adjvex[i] is gradually established, that is, the vertex in the minimum spanning tree.

4. Find the minimum value in lowcost [], assuming the final minimum value lowcost[j], then
Record the value of j with K. Then set adjvex[i] to K (here K vertex is included in the spanning tree), and lowcost[k] to 0 (that is, K is already in the spanning tree, of course, the distance to the tree is 0, when 0, it means no further processing).

5. If the weight of K to the j vertex outside the spanning tree is less than lowcost[j], update lowcost[j] to arc[k][j].

6. At the end of one cycle, the value of adjvex[i] is determined, and the value of lowcost [] is updated for the next cycle (at the beginning of each new cycle, the value of lowcost [] is the minimum weight from the previous generation tree to each vertex).

`1 #include <iostream> 2 #include <string> 3 #define MAX 100000 4 #define INFINITY 65535 5 6 using namespace std; 7 8 struct GNode 9 { 10 int V, W; 11 int G[MAX][MAX]; 12 }; 13 typedef struct GNode* gptr; 14 gptr g = new struct GNode; 15 int Count = 1; 16 bool f[MAX] = { false }; 17 void dfs(int i); 18 int main() 19 { 20 int mon = 0; 21 int V, W; 22 int adj[MAX] = { 0 }; 23 int low[MAX] = { 0 }; 24 cin >> V >> W; 25 g->V = V; g->W = W; 26 if (g->V-1 > g->W) 27 { 28 cout << "-1";return 0; 29 } 30 for (int i = 1; i <= g->V; i++) 31 for (int j = 1;j <= g->V; j++) 32 g->G[i][j] = g->G[j][i] = INFINITY; 33 for (int i = 1; i <= g->W; i++) 34 { 35 int c1, c2, temp; 36 cin >> c1 >> c2 >> temp; 37 g->G[c1][c2] = g->G[c2][c1] = temp; 38 } 39 dfs(1); 40 if (Count != g->V) 41 { 42 cout << "-1"; 43 return 0; 44 } 45 for (int i = 1;i <= g->V; i++) 46 { 47 low[i] = g->G[1][i]; 48 } 49 adj[1] = 1; 50 low[1] = 0; 51 for (int i = 2; i <= g->V; i++) 52 { 53 int j = 2;int k = 0; 54 int min = INFINITY; 55 while (j <= g->V) 56 { 57 if (low[j]!=0 && low[j] < min) 58 { 59 min = low[j]; 60 // low[j] = k; 61 k = j; 62 } 63 64 j++; 65 } 66 mon += min; 67 low[k] = 0; 68 adj[i] = k; 69 for (int j = 1; j <= g->V; j++) 70 { 71 if (low[j]!=0 && g->G[k][j] < low[j]) 72 { 73 low[j] = g->G[k][j]; 74 75 } 76 } 77 } 78 79 cout << mon; 80 return 0; 81 } 82 void dfs(int i) 83 { 84 for (int j = i+1; j <= g->V; j++) 85 { 86 87 if (g->G[i][j] != INFINITY) 88 { 89 if (!f[j]) 90 { 91 f[j] = true; 92 dfs(j); 93 Count++; 94 } 95 } 96 if (j == g->V) return; 97 } 98 99 return; 100 }`