Prim algorithm

The priM algorithm of minimum spanning tree has not been learned, and it seems that the most short circuit will also use this idea, so today I learned, looked for a lot of blogs, algorithm diagrams are quite good, but the code implementation is very complex, and finally found a template problem solving blog to read the code implementation.

//https://blog.csdn.net/hesorchen
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <string>
#include <queue>
#include <stack>
#include <list>
#include <map>
#include <set>
using namespace std;
#define ll long long
#define endl "\n"
#define INF 0x3f3f3f3f
#define mod 1000000007
#define MAX 55

int n, m;
int mp[MAX][MAX]; // Adjacency matrix
int d[MAX];       // Represents the distance between nodes outside each graph and the spanning tree
int t[MAX];       // Record the nodes inside and outside the spanning tree
int prim(a)
{
    int ans = 0;
    d[1] = 0; // Assume node 1 is inside the spanning tree and everything else is outside the tree
    int v;
    while (1)
    {
        v = - 1;
        for (int i = 1; i <= n; i++)
        {
            if(! t[i] && (v ==- 1 || d[i] < d[v])) // Find the node v closest to the spanning tree
                v = i;
        }
        if (v == - 1) // If all nodes are already in the spanning tree, the minimum spanning tree has been generated
            break;
        t[v] = 1; // add node v to the node
        ans += d[v];
        for (int i = 1; i <= n; i++) // After adding node V to the spanning tree, update the distance between the node connected to v and the spanning tree!!
            d[i] = min(d[i], mp[i][v]);
    }
    return ans;
}
int main(a)
{
    while (cin >> n && n)
    {
        cin >> m;
        for (int i = 1; i <= n; i++) // Initialize the adjacency matrix
        {
            for (int j = 1; j <= n; j++)
                if (i == j)
                    mp[i][j] = 0;
                else
                    mp[i][j] = INF;
        }
        while (m--)
        {
            int x, y, z;
            cin >> x >> y >> z; // Enter the update adjacency matrix
            if (mp[x][y] > z)
                mp[x][y] = mp[y][x] = z;
        }
        for (int i = 1; i <= n; i++)
            d[i] = INF;
        fill(t, t + MAX, 0);
        cout << prim() << endl;
    }
    return 0;
}
Copy the code

Today’s efficiency is low, only look at such an algorithm… (So impetuous!!)