Prim’s Algorithm For Minimum Spanning Tree In C Programming

#include
#include
#define size 20
#define infi 9999

void prim(int L[][size],int node)
{
 int T[size],i,j,k;
 int min_dist,v1,v2,total=0;

 for(i=1;i<= node;i++)
  T[i]=0;
  
 printf("\n--------------------------------");
 printf("\n The minimum spanning tree is:");
 printf("\n--------------------------------");
 T[1]=1;
 for(k=2;k<= node;k++)
 {
  min_dist=infi;
  for(i=1;i<= node;i++)
  {
   for(j=1;j<= node;j++)
   {
    if(L[i][j]&&((T[i]&&!T[j])||(!T[i]&&T[j])))
    {
     if(L[i][j] < min_dist)
     {
      min_dist=L[i][j];
      v1=i;
      v2=j;
     }
    }
   }
  }


printf("\n Edge (%d %d)and weight= %d",v1,v2,min_dist);
T[v1]=T[v2]=1;
total=total+min_dist;
}
printf("\n -----------------------------------");
printf("\n total path Length is= %d",total);
printf("\n ------------------------------------");
}
void main()
{
 int L[size][size],node;
 int v1,v2,length,i,j,n;
 clrscr();
 printf("\n--------------------------------------");
 printf("\n         PRIM`s ALGORITHMS            ");
 printf("\n--------------------------------------\n");

 printf("\n Enter Number of nodes in the Graph:");
 scanf("%d",&node);

 printf("\n Enter Number of Edges in the Graph:");
 scanf("%d",&n);

 for(i=1;i<= node;i++)
  for(j=1;j<= node;j++)
   L[i][j]=0;

 printf("\n--------Enter edges and weight--------");

 for(i=1;i<= n;i++)
 {
  printf("\nEnter edge by v1 and v2:");
  scanf("%d %d",&v1,&v2);
  printf("\nEnter Weight from %d to %d:",v1,v2);
  scanf("%d",&length);
  L[v1][v2]=L[v2][v1]=length;
 }

 printf("\n Enter any key to see Minimum Spanning Tree?");
 getch();
 prim(L,node);
getch();
}

OUTPUT

----------------------------------------------------
PRIM`s MINIMUM SPANNING TREE ALGORITHM
----------------------------------------------------
 Enter Number of nodes in the Graph:7

 Enter Number of Edges in the Graph:12

--------Enter edges and length----------

Enter edge in form {v1,v2}:1 2

Enter Length from 1 to 2:1

Enter edge in form {v1,v2}:1 4

Enter Length from 1 to 4:4

Enter edge in form {v1,v2}:2 3

Enter Length from 2 to 3:2

Enter edge in form {v1,v2}:2 4

Enter Length from 2 to 4:6

Enter edge in form {v1,v2}:2 5

Enter Length from 2 to 5:4

Enter edge in form {v1,v2}:3 6

Enter Length from 3 to 6:6

Enter edge in form {v1,v2}:3 5

Enter Length from 3 to 5:5

Enter edge in form {v1,v2}:4 5

Enter Length from 4 to 5:3

Enter edge in form {v1,v2}:4 7

Enter Length from 4 to 7:4

Enter edge in form {v1,v2}:5 6

Enter Length from 5 to 6:8

Enter edge in form {v1,v2}:5 7

Enter Length from 5 to 7:7

Enter edge in form {v1,v2}:6 7

Enter Length from 6 to 7:3

 Enter any key to see Minimum Spanning Tree?
----------------------------------------------------
 The minimum spanning tree is:
----------------------------------------------------
 Edge {1,2} and Weight=1
 Edge {2,3} and Weight=2
 Edge {1,4} and Weight=4
 Edge {4,5} and Weight=3
 Edge {4,7} and Weight=4
 Edge {6,7} and Weight=3
----------------------------------------------------
 Total Minimum path Length is= 17
----------------------------------------------------