 # Prim algorithm

Posted on Aug. 8, 2022, 5:55 p.m. by 梁家銘
Category: The code of life Tag: algorithm

## Minimum spanning tree subproblem:POJ 1287

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.

## Prim is a very simple algorithmKeep looking for the current distance`The generated tree`The smallest node is added to the tree, until all the nodes are in the tree.

Ps: If the algorithm is not clear, take a look at this blog's illustration: Portal.

## Know the train of thought, next look at the above template problem, and then carefully, patient simulation of the following code should be no problem.

``````//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 = 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!!)

Search
Categories