Minimum spanning tree Prim’s algorithm

Minimum spanning tree Prim’s algorithm

In the last post, we discussed how to find minimum spanning tree in a graph using Kruskal algorithm. Let’s take a look at another algorithm to find the minimum spanning tree in a graph, this algorithm is called Prim’s algorithm. Problem statement remains the same as the Kruskal algorithm, given a graph with weighted edges, find MST in it.

Prim’s algorithm for minimum spanning tree

Basic idea pf Prim’s algorithm is to maintain two sets of nodes of the graph, one contains all the nodes which are already included into the minimum spanning tree and the other contains all nodes which are not included in MST yet. Now find an edge with least weight which connects any node in the first set to any node in the second set. Such an edge is commonly called as cut.

Let two sets be A which includes all vertices of the graph which are included in MST and V is set which contains all vertices which are not included in MST yet. Let S be set of all vertices of a graph.

To start with A will be empty and V will be equal to S. Start with any one vertex and add it to A. Also, the cost of reaching any node initially is INFINITE. Once we add the vertex to A, update the cost of all neighbor vertex based on cost to reach vertex added in A and cost of edge between this vertex and neighboring vertices. Remove the vertex from V.

Now, select an edge which is minimum and connects one vertex in A with a vertex in V, it does not form a cycle. (If both the ends of an edge are in same component of the graph there are bound form a cycle.)

Let’s see prim’s algorithm and then we will see how can we implement it.

  1. Initialize cost of each vertex with INFINITE. Except from the first vertex v where we will start.
  2. For each neighbor u, cost(u) < cost(v) + w(u,v), update the cost(u).
  3. Select a minimum cost neighbor vertex among these vertex and see if edge forms a cycle.
  4. If it forms a cycle take another vertex till we considered every neighboring vertices.
  5. If it does not form cycle, add it to MST and go to step 2.
  6. Repeat all above steps till all the vertices are not included in tree.

See the working of algorithm.
minimum spanning tree using prim's algorithm

Minimum spanning tree algorithm's implementation.

First thing we need to do is to keep track of two sets. We can do so by keeping track of each node in MST. Create an array and every time we add the node in MST, mark it as added. While considering any edge in future, just check if MST[i] is true, if it is then node is already added in MST and should not be added again.Second thing is to keep track of the cost of each node. Initially all nodes are at INFINITE cost.

As we traverse the graph, update each node's cost from the current node. Keep an array of integers initialized with INFINITE and every time we add a node in MST, update distance of neighboring nodes based on cost of edge from current node to them. Last step is to find the minimum cost edge between two sets. We can scan through the distance array which we discussed in above paragraph and get a node which has least cost and not already in MST (using the array values in discussed in paragraph 1)
Finding minimum can be implemented using min heap or priority queues, that would reduce the complexity of overall algorithm.

#include<stdio.h>
#include<stdlib.h>
 
#define NUM_NODE 6
#define MAX_VALUE 999
#define true 1
#define false 0
 
//Definition of node in adjacency list formation
typedef struct node{
    int value;
    int wt;
    struct node *next;
}Node;
 
//Edge definition for sorting and storing minimum spanning tree
typedef struct edge{
    int start;
    int end;
    int wt;
}Edge;
 
Node *graph[NUM_NODE + 1];
 
//This function creates a node in adjancency list representation with weight 
Node * createNode(int j, int wt){
 
    Node *newNode = (Node *)malloc(sizeof(Node));
    if(newNode){
        newNode->value = j;
        newNode->next = NULL;
        newNode->wt = wt;
    }
    else{
        printf("\n Node cannot be allocated");
    }
    return newNode;
}
//Adds edge in graph
void addEdge(int i, int j, int wt){
 
    Node *currentNode = graph[i];
    if(currentNode == NULL){
        graph[i] = createNode(j, wt);
    }
    else{
        while(currentNode->next){
            currentNode = currentNode->next;
        }
        currentNode->next = createNode(j, wt);
    }
}

void updateWeights(int currentVertex, int weights[], 
                   int predecessors[], int visited[]){
  	
  	Node *currentNode = graph[currentVertex];
  	if(currentNode){
  		//update distance for all neighbor nodes
  		Node * itr = currentNode->next;
  		while(itr){
  			if(weights[itr->value] >  itr->wt && visited[itr->value] == false ){
  				weights[itr->value] =  itr->wt;
  				predecessors[itr->value] = currentVertex;
			}
  			itr = itr->next;
  		}
  	}
  }
  
int getMinimumVertex( int weights[], int visited[], int numNodes ){
    int currentMinWeight = MAX_VALUE;
    int currentMinVertex = 1; 
    for( int i = 2; i<=numNodes; i++ ){
      if( !visited[i] && weights[i] < currentMinWeight  ){
        currentMinWeight = weights[i];
        currentMinVertex = i;
      }
    }
    return currentMinVertex;
  }
 
//Real implementation of prims algorithm
int primsMSTAlgorithm(Node * graph[], int numNodes){
 
    //Step 1 : Initialize all arrays
    int weights[numNodes+1];
    int visited[numNodes+1];
    int predecessors[numNodes+1];
 
    for( int i=1; i<=numNodes; i++ ){
      weights[i] = MAX_VALUE;
    }
    for( int i=1; i<=numNodes; i++ ){
      visited[i] = 0;
    }
    for( int i=1; i<=numNodes; i++ ){
      predecessors[i] = MAX_VALUE;
    }
    
    weights[1] = 0;
 	int totalCost = 0;
   //Step 2 : 
    for( int i=0; i <=numNodes; i++ ){
      //Greedy strategy
      int closestVertex      = getMinimumVertex( weights, visited, numNodes );
      totalCost+= weights[closestVertex];
      visited[closestVertex] = true;
      updateWeights( closestVertex, weights, predecessors, visited  );
    }
	return totalCost;    
}
  
//Driver program
int main(){
 
    int i;
    for(i=1; i<=NUM_NODE; i++){
        graph[i] = createNode(i,0);
    }
    addEdge(1,2,4);
    addEdge(2,1,4);
    addEdge(2,3,3);
    addEdge(3,2,3);
    addEdge(4,3,2);
    addEdge(3,4,2);
    
    addEdge(4,1,3);
    addEdge(1,4,3);
    addEdge(4,5,3);
    addEdge(5,4,3);
    
    addEdge(6,5,1);
    addEdge(5,6,1);
    
    addEdge(1,6,5);
    addEdge(6,1,5);
    
    addEdge(2,5,4);
    addEdge(5,2,4);
 
    int totalCost = primsMSTAlgorithm(graph, NUM_NODE);
 	printf("Cost of minimum spanning tree : %d", totalCost);
    return 0;
}

The complexity of Prim's algorithm to find minimum spanning tree in graph is O(V2).

Please share if there is anything is wrong or missing. If you are preparing for an interview and need 1 to 1 coaching for preparation, please reach out to us at communications@algorithmsandme.com or book a free session with us.