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:
 




Comments

Post a Comment

Popular posts from this blog

Write a Program to Add two 3x3 Matrix using C

Image
#include<stdio.h> void main () { int a [ 3 ][ 3 ], b [ 3 ][ 3 ], s [ 3 ][ 3 ], i , j ; printf ( "Enter the values of 1st matrix" ); for ( i = 0 ; i < 3 ; i ++ ) { for ( j = 0 ; j < 3 ; j ++ ) { scanf ( "%d" , & a [ i ][ j ]); } } printf ( "Enter the values of 2nd matrix" ); for ( i = 0 ; i < 3 ; i ++ ) { for ( j = 0 ; j < 3 ; j ++ ) { scanf ( "%d" , & b [ i ][ j ]); } } for ( i = 0 ; i < 3 ; i ++ ) { for ( j = 0 ; j < 3 ; j ++ ) { s [ i ][ j ] = a [ i ][ j ] + b [ i ][ j ]; } } printf ( " \n The Sum is : \n " ); for ( i = 0 ; i < 3 ; i ++ ) { printf ( " \n\n " ); for ( j = 0 ; j < 3 ; j ++ ) { printf ( " \t %d" , s [ i ][ j ]); } ...
Read more

C program for Unit Conversion

Image
/* Convert Celsius to Fahrenheit */ #include<stdio.h> void main() {     float c,f;     printf("Enter the temperature in Celcius: ");     scanf("%f",&c);     f = c * 9/5 + 32;     printf("Temperature in Farenheit: %f",f); } /* Convert Farenheit to Celcius */ #include<stdio.h> void main() {     float c,f;     printf("Farenheit : ");     scanf("%f",&f);     c = (f - 32) * 5/9;     printf("Celcius: %f",c);  } /*Convert Meter to Feet*/ #include<stdio.h> void main() {     float m,f;     printf("Meter : ");     scanf("%f",&m);     f = 3.2808399 * m;     printf("Feet: %f",f); } /* Convert Feet to Meter */ #include<stdio.h> void main() {     float m,f;     printf("Feet : ");     scanf("%f",&f);     m = f / 3.2808399;     printf("Meter: %f",m); } /*Convert...
Read more

Write a Program to Add two 5x5 Matrix using C

Image
#include<stdio.h> void main() {   int a[5][5],b[5][5],c[5][5];   int i,j;   for(i=0;i<5;i++)   {     printf("\nEnter elements of %d row of first Matrix: ",i+1);     for(j=0;j<5;j++)       scanf("%d",&a[i][j]);   }   for(i=0;i<5;i++)   {     printf("\nEnter elements of %d row of second Matrix: ",i+1);     for(j=0;j<5;j++)       scanf("%d",&b[i][j]);   }   printf("\nSum of Matrix:\n\n");   for(i=0;i<5;i++)   {     for(j=0;j<5;j++)     {       c[i][j]=a[i][j]+b[i][j];       printf("%3d ",c[i][j]);     }     printf("\n");   } }
Read more