Kruskal's Agorithm

6. Find Minimum Cost Spanning Tree of a given undirected graph using Kruskal’s algorithm.

#include<stdio.h>

void kruskals();
int parent[10],cost[10][10],ne,i,j,n,min,a,b,u,v,mincost=0;

void main()
{
  printf("\n\n*********KRUSKALS ALGORITH*********\n\n");
  printf("Enter the number of nodes:");
  scanf("%d",&n);
  printf("\n\nEnter the cost matrix\n");
  for(i=1;i<=n;i++)
   {
     for(j=1;j<=n;j++)
      {
        scanf("%d",&cost[i][j]);
      }
   }
  printf("\n\nThe entered cost matrix is\n");
  for(i=1;i<=n;i++)
   {
     for(j=1;j<=n;j++)
      {
         printf("%d\t",cost[i][j]);
      }
      printf("\n");
   }
   kruskals();
   printf("\n\nThe minimum spanning tree cost is %d",mincost);
   printf("\n\n************ ************** *************");
}

void kruskals()
{
  ne=1;
  while(ne<n)
  {
    for(i=1,min=999;i<=n;i++)
      {
       for(j=1;j<=n;j++)
        {
          if(cost[i][j]<min)
           {
             min=cost[i][j];
             a=u=i;
             b=v=j;
           }
        }
      }
  while(parent[u])
      u=parent[u];
  while(parent[v])
      v=parent[v];
  if(u!=v)
   {
     printf("%d> minimum edge from %d to %d is %d\n\n",ne++,a,b,min);
     mincost+=min;
     parent[v]=u;
   }
   cost[a][b]=cost[b][a]=999;
  }
}



OUTPUT:

Enter the number of nodes:5

Enter the cost matrix
0  1  2  999  6  1  0  3  999  999  2  3  0   4  999  999  999  4  0  5  6  999  999  5  0