Prim's Algorithm

Prim's algorithm is very similar to Kruskal's: whereas Kruskal's "grows" a forest of trees, Prim's algorithm grows a single tree until it becomes the minimum spanning tree. Both algorithms use the greedy approach - they add the cheapest edge that will not cause a cycle. But rather than choosing the cheapest edge that will connect any pair of trees together, Prim's algorithm only adds edges that join nodes to the existing tree. (In this respect, Prim's algorithm is very similar to Dijkstra's algorithm for finding shortest paths.)

Prim's algorithm works efficiently if we keep a list d[v] of the cheapest weights which connect a vertex, v, which is not in the tree, to any vertex already in the tree. A second list pi[v] keeps the index of the node already in the tree to which v can be connected with cost, d[v].

int *MinimumSpanningTree( Graph g, int n, double **costs ) {
   Queue q;
   int u, v;
   int d[n], *pi;
   q = ConsEdgeQueue( g, costs );
   pi = ConsPredList( n );
   for(i=0;i<n;i++) {
     d[i] = INFINITY;
     }
   /* Choose 0 as the "root" of the MST */
   d[0] = 0;
   pi[0] = 0;
   while ( !Empty( q ) ) {
     u = Smallest( g );
     for each v in g->adj[u] {
       if ( (v in q) && costs[u][v] < d[v] ) {
         pi[v] = u;
         d[v] = costs[u][v];
         }
       }
     }
   return pi;
   }

The steps are:

1. The edge queue is constructed
2. A predecessor list of predecessors for each node is constructed.
3. "Best" distances to each node are set to infinity.
4. Choose node 0 as the "root" of the MST (any node will do as the MST must contain all nodes),
5. While the edge queue is not empty,
   1. Extract the cheapest edge, u, from the queue,
   2. Relax all its neighbours - if the distance of this node from the closest node in the MST formed so far is larger than d[u][v], then update d[u][v] and set v's predecessor to u.
6. Return the predecessor list.

The time complexity is O(VlogV + ElogV) = O(ElogV), making it the same as Kruskal's algorithm. However, Prim's algorithm can be improved using Fibonacci Heaps (cf Cormen) to O(E + logV).

Key terms

Predecessor list

A data structure for defining a graph by storing a predecessor for each node with that node. Thus it uses a single array of integers to define a sub-graph of a graph.

Fibonacci Heaps

See Cormen, chapter 21.

The time complexity is O(VlogV + ElogV) = O(ElogV), making it the same as Kruskal's algorithm. However, Prim's algorithm can be improved using Fibonacci Heaps (cf Cormen) to O(E + logV).