# 7-10 road to village (30 points) - minimum spanning tree prim

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     }
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;
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 }``````

Tags: less

Posted on Sun, 03 May 2020 18:57:54 -0700 by Ionisis