Write a C Program to Implement Prim’s Algorithm and find the Minimum Spanning Tree (MST) for the following Graph.
Algorithm:
visit[1] <- 1;
while( p < n )
{
min=999;
for( i<- 1 to n )
{
for( j <- 1 to n )
{
if(cost[i][j] < min)
{
if( visit[i]!= 0 )
{
Min <- cost[i][j];
a <- u <- i;
b <- v <- j;
}
}
}
}
if( visit[u] = 0 OR visit[v] = 0 )
{
Print Edge of MST;
mincost <- mincost+min;
visit[b] <- 1;
}
cost[a][b] <- cost[b][a] <- inf;
}
Print Total Minimum Cost;
Program:
#include<stdio.h>
#include<conio.h>
#define inf 999
int cost[10][10],visit[10]={0};
int n,p=1,i,u,v,j,min,a,b,mincost;
void main()
{
clrscr();
printf("Enter node value: ");
scanf("%d",&n);
printf("Enter the adjacency matrix: \n");
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
scanf("%d",&cost[i][j]);
if( cost[i][j]==0 && i!=j )
cost[i][j]=inf;
}
}
printf("Entered Matrix: ");
for(i=1;i<=n;i++)
{
printf("\n");
for(j=1;j<=n;j++)
{
printf("%d\t",cost[i][j]);
}
}
visit[1]=1;
while(p<n)
{
for(i=1,min=999;i<=n;i++)
{
for(j=1;j<=n;j++)
{
if(cost[i][j]<min)
{
if (visit[i]!=0)
{
min=cost[i][j];
a=u=i;
b=v=j;
}
}
}
}
if(visit[u]==0 || visit[v]==0)
{
printf("\nEdge %d:(%d-%d) Cost=%d\n",p++,a,b,min);
mincost=mincost+min;
visit[b]=1;
}
cost[a][b]=cost[b][a]=inf;
}
printf("\n Minimum cost=%d",mincost);
getch();
}
Output:
0 Comments