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

 

Tags: less

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