Prim

Prim's Algorithm is a method to construct a minimal spanning tree. For example, this can be used when one wants to determine the minimal cost of connecting a number of cities to a water source (the cities are the nodes and the distances between the cities determine the cost to lay a pipeline between two cities). The steps of the most basic form of the algorithm are as follows:

• Iteratively find the closest node to that one and add the edge between them.
• Let the distance from each node not in the tree to the tree be the edge of minimal weight between that node and some node in the tree.
• At each step, find a node not currently within the tree which is closest to the tree and add the minimum weight edge from that node to some node in the tree.
• Incorporate that node as part of the tree.

Basically, the algorithm greedily builds the minimal spanning tree by selecting the closest node to a tree that works.

Here is the \$O(V^2)\$ implementation of the algorithm. The assumed input format is:
V
[adjacency matrix of distances between verticies]

This is the basic implementation with an adjacency matrix.

```#include <iostream>
#include <fstream>
#define MAXN 1001
#define INFTY (9223372036854775807LL)
using namespace std;

ifstream fin ("mst.in");
ofstream fout ("mst.out");

main () {
int V, mstsize = 1, mstcost = 0, curnode = 0;
long long dist[MAXN], adj[MAXN][MAXN], mind = INFTY;
bool intree[MAXN];
fin >> V;
for (int i = 0; i < V; i++)
for (int j = 0; j < V; j++)

// Set all distances to infinity and all nodes as outside the tree initially
for (int i = 0; i < V; i++) {
dist[i] = INFTY;
intree[i] = false;
}

// Add node #0 to the tree, update current distances from tree
intree[0] = true;
for (int i = 0; i < V; i++)

for (int mstsize = 0; mstsize < V; mstsize++) {
mind = INFTY;

// Find node with minimum distance to the tree
for (int i = 0; i < V; i++) {
if (dist[i] < mind && !intree[i])
mind = dist[i], curnode = i;
}

// Add the new node to the tree
mstcost += dist[curnode];
intree[curnode] = true;

// Update distances, now that the new node has been added
for (int i = 0; i < V; i++)
if (dist[i] > adj[curnode][i] && curnode != i)