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]

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); }

page revision: 3, last edited: 03 Nov 2008 04:51