To create a node set of connected parts, Prim algorithm adopts a greedy strategy to add the point with the minimum edge weight from the set to the set each time and iteratenAnd then finally connect all the points.

Subject train of thought

Dist [I] : the minimum distance between node I and the set. St [I] : indicates whether node I has been added to the set.

  1. Outer loop iterationnAdd all the points to the set.
  2. Each time I iterate over the point closest to the set, if the point closest to the set is zero0x3f(infinity), it means that the minimum spanning tree cannot be generated, and impossible is output; If the distance is not zero0x3f, represents reachable, and the edge weight is increased.
  3. After the new node is added to the set, the new node is used as the fulcrum to update the distance between all other nodes and the set.

C + + code

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;

const int N = 510, INF = 0x3f3f3f3f;

int n, m;
int g[N][N];
int dist[N];
int st[N];

void Prim(a)
{
    memset(dist, 0x3f.sizeof dist);

    int res = 0;
    for (int i = 0; i < n; i++)
    {
        int t = - 1;
        for (int j = 1; j <= n; j++)
        {
            if(! st[j] && (t ==- 1|| dist[t] > dist[j])) { t = j; }}if (i && dist[t] == INF)
        {
            cout << "impossible";
            return;
        }

        if (i)
        {
            res += dist[t];
        }
        st[t] = true;

        for (int j = 1; j <= n; j++)
        {
            dist[j] = min(dist[j], g[t][j]);
        }
    }
    cout << res;
}

int main(a)
{
    cin.tie(0);
    ios::sync_with_stdio(false);

    memset(g, 0x3f.sizeof g);

    cin >> n >> m;
    while (m--)
    {
        int u, v, w;
        cin >> u >> v >> w;
        g[u][v] = g[v][u] = min(g[u][v], w);
    }

    Prim(a);return 0;
}
Copy the code