Prim Algorithm

Given a connected weighted graph G, it is often desired to create a spanning tree T for G such that the sum of the weights of the tree edges in T is as small as possible. Such a tree is called as minimum spanning tree and represents the most inexpensive way of connecting all the nodes in G. There are a number of techniques for creating a minimum spanning tree for a weighted graph. The first of these, Prim’s algorithm, discovered independently by Prim and Dijkstra, is very much like Dijkstra’s algorithm for finding shortest paths. An arbitrary node is chosen initially as the tree root (note that in an undirected graph and its spanning tree, any node can be considered the tree root and the nodes adjacent to it as its sons). The nodes of the graph are then appended to the tree one at a time until all nodes of the graph are included.

The node of the graph added to the tree at each point is that node adjacent to a node of the tree by an arc of minimum weight. The arc of minimum weight becomes a tree arc connecting the new node to the tree. When all the nodes of the graph have been added to the tree, a minimum spanning tree has been constructed for the graph.

To see that this technique creates a minimum spanning tree, consider a minimum spanning tree T for the graph and consider the partial tree PT built by Prim’s algorithm.

Suppose that (a, b) is the minimum-cost arc from nodes in PT to nodes not in PT, and suppose that (a, b) is not in T. Then, since there is a path between any two graph nodes in a spanning tree, there must be an alternate path between a and b in T that does not include arc (a, b). This alternate path P must include an arc (x, y) from a node in PT to a node outside of PT. Let us assume that P contains sub-paths between a and x and between y and b.

Now consider what would happen if we replaced arc (x, y) in T with (a, b) to create NT. We claim that NT is also a spanning tree. To prove this, we need to show two things: that any two nodes of the graph are connected in NT and that NT does not contain a cycle, that is, that there is only one path between any two nodes in NT.

Since T is a spanning tree, any two nodes, m and n, are connected in T. If the path between them in T does not contain (x, y), the same path connects them in NT. If the path between them in T does contain (x, y), consider the path in NT formed by the sub-path in T from m to x, the sub-path in P (which is in T) from x to a, the arc (a, b), the sub-path in P from b to y, and the sub-path in T from y to n. This is a path from m to n in NT. Thus any two nodes of the graph are connected in NT.

To show that NT does not contain a cycle, suppose that it did. If the cycle does not contain (a, b) then the same cycle would exist in T. But that is impossible, since T is a spanning tree. Thus the cycle must contain (a, b). Now consider the same cycle with arc (a, b) replaced with the sub-path of P between a and x, the arc (x, y), and the sub-path in P between y and b. The resulting path must also be a cycle and is a path entirely in T. But, again, T cannot contain a cycle. Therefore NT also does not contain a cycle.

NT has thus been shown to be a spanning tree. But NT must have lower cost than T, since (a, b) was chosen to have lower cost than (x, y). Thus it is not a minimum spanning tree unless it includes the lowest weight arc from PT to nodes outside PT. Therefore any arc added by Prim’s algorithm must be part of a minimum spanning tree.

The crux of the algorithm is a method for efficient determination of the “closest” node to a partial spanning tree. Initially, when the partial tree consists of a single root node, the distance of any other node n from the tree, distance[n], is equal to weight(root ,n). When a new node, current, is added to the tree, distance[n] is modified to the minimum of distance[n] and weight(current, n). The node added to the tree at each point is the node whose distance is lowest. For nodes m in te tree, distance[m] is set to infinity, so that a node outside the tree is chosen as closest. An additional array closest[n] points to the node in the tree such that distance[n] = weight(closest[n], n); that is, the node in the tree closest to n. If two nodes, x and y, are not adjacent, weight(x, y) is also infinity.

C++ Implementation: Program for creating minimum spanning tree using Prim’s algorithm.

#include<iostream.h> #include<process.h> #define MAX 10 #define TEMP 0 #define PERM 1 #define FALSE 0 #define TRUE 1 #define infinity 9999 struct node {      int predecessor;      int dist; /*Distance from predecessor */      int status; }; struct edge {      int u;      int v; }; int create_graph(); void display(); int maketree(edge [],int *); int all_perm(node [] ); int adj[MAX][MAX]; int n; void main() {      int i,j;      int path[MAX];      int wt_tree,count;      struct edge tree[MAX];      create_graph();      cout<<“Adjacency matrix is :n”;      display();      count = maketree(tree,&wt_tree);      cout<<“Weight of spanning tree is : “<<wt_tree;      cout<<“Edges to be included in spanning tree are : n”;      for(i=1;i<=count;i++)      {         cout<<tree[i].u<<” -> n”;         cout<<tree[i].v<<“n”;      } }/*End of main()*/ int create_graph() {      int i,max_edges,origin,destin,wt;      cout<<“Enter number of vertices : “;      cin>>n;      max_edges=n*(n-1)/2;      for(i=1;i<=max_edges;i++)      {         cout<<“Enter edge “<< i <<” (0 0 to quit) : “;         cin>>origin;         cout<<“t”;         cin>>destin;         if((origin==0) && (destin==0))            break;         cout<<“Enter weight for this edge : “;         cin>>wt;         if( origin > n || destin > n || origin<=0 || destin<=0)         {            cout<<“Invalid edge!n”;            i–;         }         else         {            adj[origin][destin]=wt;            adj[destin][origin]=wt;         }      }      if(i<n-1)      {         cout<<“Spanning tree is not possiblen”;         exit(1);      } }/*End of create_graph()*/ void display() {      int i,j;      for(i=1;i<=n;i++)      {         for(j=1;j<=n;j++)         cout<<“t”<<adj[i][j];         cout<<“n”;      } }/*End of display()*/ int maketree(edge tree[MAX],int *weight) {      node state[MAX];      int i,k,min,count,current,newdist;      int m;      int u1,v1;      *weight=0;      /*Make all nodes temporary*/      for(i=1;i<=n;i++)      {         state[i].predecessor=0;         state[i].dist = infinity;         state[i].status = TEMP;      }      /*Make first node permanent*/      state[1].predecessor=0;      state[1].dist = 0;      state[1].status = PERM;      /*Start from first node*/      current=1;      count=0; /*count represents number of nodes in tree */      while( all_perm(state) != TRUE ) /*Loop till all the nodes become PERM*/      {         for(i=1;i<=n;i++)         {            if ( adj[current][i] > 0 && state[i].status == TEMP )            {               if( adj[current][i] < state[i].dist )               {                  state[i].predecessor = current;                  state[i].dist = adj[current][i];               }            }      }      /*Search for temporary node with minimum distance and make it current node*/      min=infinity;      for(i=1;i<=n;i++)      {         if(state[i].status == TEMP && state[i].dist < min)         {            min = state[i].dist;            current=i;         }      }      state[current].status=PERM;      /*Insert this edge(u1,v1) into the tree */      u1=state[current].predecessor;      v1=current;      count++;      tree[count].u=u1;      tree[count].v=v1;      /*Add wt on this edge to weight of tree */      *weight=*weight+adj[u1][v1];      }/*End of while*/      return (count); }/*End of maketree()*/ /*This function returns TRUE if all nodes are permanent*/ int all_perm(node state[MAX] ) {      int i;      for(i=1;i<=n;i++)      if( state[i].status == TEMP )         return FALSE;      else         return TRUE; }/*End of all_perm()*/