Krushkals algorithm Code in C Language

Krushkals algorithm Code in C Language Code

 #include  
 #include  
 #define max 50  
 void create_heap(int arr[][3],int n)  
 {  
   int k,heap,j;  
   int temp[3];  
   for(int i=(n/2)-1;i>=0;--i)  
   {  
     k=i;  
     temp[0]=arr[k][0];  
     temp[1]=arr[k][1];  
     temp[2]=arr[k][2];  
     heap=0;  
     while( heap!=1 && ( (2*k +1)      {  
       j=2*k+1;  
       if(j<n-1) <br="">       if(arr[j][2]>arr[j+1][2])  
         j++;  
       if(arr[k][2]<arr[j][2]) <br="">         heap=1;  
       else  
       {  
         arr[k][0]=arr[j][0];  
         arr[k][1]=arr[j][1];  
         arr[k][2]=arr[j][2];  
         k=j;  
         heap=0;  
       }  
     }  
     arr[k][0]=temp[0];  
     arr[k][1]=temp[1];  
     arr[k][2]=temp[2];  
   }  
 }  
 void input(int arr[][3])  
 {  
   char ch;  
   int s,d,w;  
   int i=0;  
   while(1)  
   {  
     printf("Do you want to enter any edge?:");  
     flushall();  
     scanf("%c",&ch);  
     if(ch=='n'||ch=='N')  
       break;  
     printf("Source:");  
     flushall();  
     scanf("%d",&s);  
     printf("Destination:");  
     flushall();  
     scanf("%d",&d);  
     printf("Weight:");  
     flushall();  
     scanf("%d",&w);  
     arr[i][0]=s;  
     arr[i][1]=d;  
     arr[i++][2]=w;  
   }  
 }  
 void heap_delete(int arr[][3],int *n)  
 {  
   (*n)--;  
   arr[0][0]=arr[*n][0];  
   arr[0][1]=arr[*n][1];  
   arr[0][2]=arr[*n][2];  
   create_heap(arr,*n);  
 }  
 int find(int i,int parent[20])  
 {  
   while(parent[i]!=-1)  
     i=parent[i];  
   return i;  
 }  
 void main()  
 {  
   clrscr();  
   int n;  
   printf("Enter the no of veritces\n");  
   int edge[max][3],parent[max];  
   scanf("%d",&n);  
   input(edge);  
   int t[3];  
   //create_heap(edge,n);  
   create_heap(edge,n);  
   int u,v;  
   int n1=n;  
   int result[max][3];  
   for(int i=0;i<n;++i) <br="">     parent[i]=-1;  
   for(i=0;i<n1-1;++i) <br="">   {  
     t[0]=edge[0][0];  
     t[1]=edge[0][1];  
     t[2]=edge[0][2];  
     u=find(t[0],parent);  
     v=find(t[1],parent);  
     if(u!=v)  
     {  
       parent[u]=v;  
       result[i][0]=t[0];  
       result[i][1]=t[1];  
       result[i][2]=t[2];  
     }  
     heap_delete(edge,&n);  
   }  
   printf("S\tD\tW\n");  
   for(i=0;i<n1-1;++i) <br="">     printf("%d\t%d\t%d\n",result[i][0],result[i][1],result[i][2]);  
   getch();  
 }