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:

• Start with a tree which contains only one node.
• 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]

C++

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++) 
            fin >> adj[i][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++)
        dist[i] = adj[0][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)
                dist[i] = adj[curnode][i];
    }
 
    fout << mstcost << endl;
    exit(0);
}