Prim's Algorithm

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