Sunday 17 March 2019

Krushkal Minimum spanning tree : C program

Krushkal Algorithm:
Step 1: Start
Step 2: Read a weighted Graph G(V, E)
Step 3: Let n be the number of vertices in the graph G
Step 4: Find the lowest cost edge and draw it
Step 5: Choose the next lowest cost edge 
Step 6: if a cycle is formed if this lowest cost edge is drawn then
                Take the next lowest cost edge
Step 7: else
                 Draw the edge
Step 8: Go to step 3 until n-1 edges are drawn
Step 9: STOP
 ===========================================================
 Program:

#include<stdio.h>
int find(int i);
void union1(int,int);
int parent[10];
struct sample
{
  int u;
  int v;
  int cost;
};
typedef struct sample krushkals;
int sample(krushkals[],int,int);
main()
{
  krushkals d[10];
  int n,e,i,mincost;
  printf("enter number of vertices\n");
  scanf("%d",&n);
  printf("enter number of edges\n");
  scanf("%d",&e);
  for(i=1;i<=e;i++)
  {
    printf("enter the starting vertex\n");
    scanf("%d",&d[i].u);
    printf("enter the ending vertex\n");
    scanf("%d",&d[i].v);
    printf("enter their costs\n");
    scanf("%d",&d[i].cost);
  }
   mincost=sample(d,e,n);
   printf("mincost of a spanning tree is %d",mincost);
}




int sample(krushkals d[10],int e,int n)
{
  int mincost=0;
  int j,l,k,u,v,i;
  int t[10][10];
  krushkals temp;
  for(i=1;i<e;i++)
  {
   for(j=i+1;j<=e;j++)
   {
     if(d[i].cost>d[j].cost)
     {
       temp=d[i];
       d[i]=d[j];
       d[j]=temp;
     }
   }
  }
  for(i=1;i<=n;i++)
 parent[i]=-1;
 i=1;
 l=1;
  while(i<=n-1&&l<=e)
  {
     j=find(d[l].u);
     k=find(d[l].v);
     if(j!=k)
     {
       t[i][1]=d[l].u;
       t[i][2]=d[l].v;
       printf("t[%d][1]=%d\n",i,d[l].u);
       printf("t[%d][2]=%d\n",i,d[l].v);
       printf("path is %d->%d\n",d[l].u,d[l].v);
       mincost=mincost+d[l].cost;
       i++;
       union1(j,k);
     }
     l++;
   }
   if(i!=n)
   printf("no spanning tree\n");
   else
   return mincost;
}



 int find(int i)
 {
   while(parent[i]!=-1)
   {
     i=parent[i];
   }
   return i;
}


void union1(int i,int j)
{
   parent[i]=j;
}

No comments:

Post a Comment