Design and implement C Program to find Minimum Cost Spanning Tree of a given connected undirected graph using Prim's algorithm.
#include<stdio.h>
int ne=1,min_cost=0;
void main()
{
int n,i,j,min,cost[20][20],a,u,b,v,source,visited[20];
printf("Enter the no. of nodes:");
scanf("%d",&n);
printf("Enter the cost matrix:\n");
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
scanf("%d",&cost[i][j]);
}
}
for(i=1;i<=n;i++)
visited[i]=0;
printf("Enter the root node:");
scanf("%d",&source);
visited[source]=1;
printf("\nMinimum cost spanning tree is\n");
while(ne<n)
{
min=999;
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
if(cost[i][j]<min)
if(visited[i]==0)
continue;
else
{
min=cost[i][j];
a=u=i;
b=v=j;
}
}
}
if(visited[u]==0||visited[v]==0)
{
printf("\nEdge %d\t(%d->%d)=%d\n",ne++,a,b,min);
min_cost=min_cost+min;
visited[b]=1;
}
cost[a][b]=cost[b][a]=999;
}
printf("\nMinimum cost=%d\n",min_cost);
}
OUTPUT
adminpc@adminpc-ThinkCentre-neo-50t-Gen-3:~$ gedit prims.c
adminpc@adminpc-ThinkCentre-neo-50t-Gen-3:~$ gcc prims.c
adminpc@adminpc-ThinkCentre-neo-50t-Gen-3:~$ ./a.out
Enter the no. of nodes:6
Enter the cost matrix:
999 3 999 999 6 5
3 999 1 999 999 4
999 1 999 6 999 4
999 999 6 999 8 5
6 999 999 8 999 2
5 4 4 5 2 999
Enter the root node:1
Minimum cost spanning tree is
Edge 1 (1->2)=3
Edge 2 (2->3)=1
Edge 3 (2->6)=4
Edge 4 (6->5)=2
Edge 5 (6->4)=5
Minimum cost=15
adminpc@adminpc-ThinkCentre-neo-50t-Gen-3:~$