Prims Algorithm Explained with Example and Algorithm

Let's First solve this question and understand the procedure and then change our thinking into algorithm.


So what we do is that we first choose any one vertex as our starting point.
lets choose 0th vertex as our starting point.

Then we search for the nearest vertex from starting vertex with minimum cost
In this case it will be 3rd node .
so minimum cost will be
mincost=2

Now , normally what we do is that we search for the nearest vertex from current vertex with minimum cost and when we don't get then we backtrack to previous vertex .But instead of backtracking what we can do is that we can check for the nearest vertex with minimum cost from current and previous vertex simultaneously.

So now we search for nearest vertex with minimum cost from current i.e. 3rd vertex and previous vertex i.e. 0th vertex.
so nearest vertex with minimum cost will be   2nd.
mincost=2+3=5;

Now we search for the next node from 2nd and 0th vertex with minimum cost.
select 1st which is nearest from 0th vertex with minimum cost.
mincost=2+3+4=9

Since all the vertex are visited we are done .
minimum cost to explore this graph is 9..

First Let's Construct Cost Matrix:

We are using 99 as infinity for the nodes which are not connected.

Now Let's go for Algorithm:

//t[] is solution vector

//cost[] is cost matrix which is teken from the user

//n is number of nodes.

//near[] is array which stores the nearest vertex for each node.

//Get starting vertex from the user as k and search for the nearest node from starting node and name it as l
// as user gave k and l is nearest to k so now edge k to l is selected ,so lets update mincost

mincost=cost [k,l];

//lets put edge k-l into solution vector 

t[1,1]=k;

t[1,2]=l;

//now k-l is explored , now we will find nearest from k and l  

for i:= 1 to n do 

if(cost[i,k] < cost [i,l]) then

near[i]=k;

else

near[i]=l;

//since k-l is visited we don't whether k is near to l or l is near to k  so make it 0

near[k] := near[l] := 0;

//now node 1 is done move to node 2 and keep on searching for nearest node

for i:=2 to n-1 do

{
//now we will select next node from near[] array

//Let j be an index such that near[j] != 0 and cost[j,near[j]] is min.

//j is selected with nearest in near[j]

t[i,1] := j;

t[i,2] := near[j];

mincost := mincost + cost[j,near[j]];

near[j] := 0;

//Now we need to update near matrix , since we are done with previous edge. Now other edge is selected and we have to find nearer from them.

for k:=1 to n do

if( near[k] != 0 and cost[k,near[k]] > cost[k,j])

near[k] := j;

}

Let's Write C program for Prims Algorithm:

#include<stdio.h>

int cost[100][100],n;//cost matrix for storing the graph,n=no of nodes

int t[100][2];//t is the solution vector

int near[100];//for determining the nearest nodes in the graph

int prims_Algorithm(int start_node){

int k=start_node,l=minNode(start_node);

int i,j;

int min_cost=cost[k][l];

t[1][0]=k;

t[1][1]=l;

//exploring the first 2 nodes and initializing the near array

for(i=1;i<=n;i++)

if(cost[i][k]<cost[i][l])

near[i]=k;

else

near[i]=l;

near[k]=near[l]=0; //A value 0 in near array means the node has been visited

//Exploring the Remaining nodes and constructing the tree 

for(i=2;i<=n-1;i++){

j=nextNode();

t[i][0]=j;

t[i][1]=near[j];

min_cost=min_cost+cost[j][near[j]];

near[j]=0;

//Updating the near array considering the newly visited node

for(k=1;k<=n;k++){

if(near[k]!=0 && cost[k][near[k]]>cost[k][j])

near[k]=j;

}

}

return min_cost;

}

//Function to decide the nearest node to a particular node

 int minNode(int s){

  int i,min=99,j=99;

  for(i=1;i<=n;i++){

  if(cost[s][i]<min){

  j=i;

  min=cost[s][i];

 }

 }

 return j;

 }

 

 

 //Function to decide the next node to be considered in the tree

 int nextNode(){

  int i,j,min;

  min=99;

  for(i=1;i<=n;i++){

  if(near[i]!=0 && cost[i][near[i]]<min){

  min=cost[i][near[i]];

  j=i;

 }

 }

 return j;

 }

 

 

 void main(){

  int i,j,s,p;

  printf("Enter the no of nodes ");

  scanf("%d",&n);

  printf("Enter the Adjecency represenation of the graph\n");

  for(i=1;i<=n;i++)

  for(j=1;j<=n;j++)

  scanf("%d",&cost[i][j]);

  printf("Enter the start node ");

  scanf("%d",&s);

  p=prims_Algorithm(s);

  printf("\nSolution Vector \n");

  for(i=1;i<=n-1;i++)

  printf("%d--%d\n",t[i][0],t[i][1]);

  printf("\nMinCost=%d",p);

 }