Minimal Spanning Tree~Krushkal Algorithm

Minimal Spanning Tree by Krushkal Algorithm


#include<stdio.h>
#include<malloc.h>
#define TRUE 1
#define FALSE 0
typedef struct krushkal
    {
    int svertex;
    int evertex;
    float ecost;
    }Graph;
void sort_edges(Graph *G,int);
void check_cycle(Graph *G,int,int);
int main()
{
int n,i,j,edge_count=1;
float temp;
Graph *G;
printf("\n Enter the number of vertices:\n");
scanf("%d",&n);
G=(Graph *)malloc((n*n+1)*sizeof(Graph));
printf("\n Enter the cost of the edges :\n");
printf("\n Enter cost as 999 if there is no edge between displayed vertices :\n");
for(i=1;i<=n-1;i++)
    {
    for(j=i+1;j<=n;j++)
        {
        printf("\n Enter the cost of edge %d<--->%d : ",i,j);
        scanf("%f",&temp);
        G[edge_count].ecost=temp;
        G[edge_count].svertex=i;
        G[edge_count].evertex=j;
        edge_count++;
        }
    }
edge_count--;
sort_edges(G,edge_count);
int t=0;
printf("\n Edges is ascending order is:\n");
for(i=1;i<=edge_count;i++)
        {
        if(G[i].ecost==999.0)
            t++;
        }
for(i=1;i<=edge_count-t;i++)
        {
        printf("\n Edge %d<--->%d Cost %f ",G[i].svertex,G[i].evertex,G[i].ecost);
        }
check_cycle(G,edge_count-t,n);
return 0;
}
void check_cycle(Graph *G,int edge_count, int vertices)
{
   
 int edge_ST=1,Partition[30][20],i=1,j=1,k,V1=FALSE,V2=FALSE,pelement[30],p_count=1,m,l=1,wp1,wp2,y,z,p;
 float min_cost=0.0;
 if(edge_count<vertices-1)
     {
     printf("\n No Spanning tree is possible:\n");
     return;
     }
 pelement[1]=1;
 Partition[j][pelement[1]]=G[i].svertex;
 pelement[1]++;
 Partition[j][pelement[1]]=G[i].evertex;
 printf("\n\n Edges of Minimal Spanning Tree by Krushkal Algorithm:\n");
 printf("\n%d<--->%d  ",G[i].svertex,G[i].evertex);
 min_cost +=G[i].ecost;
 i++;
 while(1)
    {
    V1=FALSE,V2=FALSE;
    for(m=1;m<=p_count;m++)
        for(k=1;k<=pelement[m];k++)
        {
        if(G[i].svertex==Partition[m][k])
            {
            V1=TRUE;
            wp1=m;
            }
        }
    for(m=1;m<=p_count;m++)
        for(k=1;k<=pelement[m];k++)
        {
        if(G[i].evertex==Partition[m][k])
            {
            V2=TRUE;
            wp2=m;
            }
        }
    if((V1==TRUE && V2==FALSE) || (V1==FALSE && V2==TRUE) ||(V1==FALSE && V2==FALSE)||((V1==TRUE && V2==TRUE) && wp1!=wp2))
        {
        printf("\n%d<--->%d  ",G[i].svertex,G[i].evertex);
         min_cost +=G[i].ecost;
        edge_ST++;
        if(V1==FALSE && V2==FALSE)
            {
            l=1;
            p_count++;
            Partition[p_count][l]=G[i].svertex;
            l++;
            Partition[p_count][l]=G[i].evertex;
            pelement[p_count]=l;
            //printf("\n New partition is created\n");
            i++;
            }
        if(V1==TRUE && V2==FALSE)
            {
            pelement[wp1]++;
            Partition[wp1][pelement[wp1]]=G[i].evertex;
            //for(k=1;k<=pelement[wp1];k++)
                //printf(" S= %d ",Partition[wp1][k]);
            //printf("\n");
            i++;
            }
        if(V1==FALSE && V2==TRUE)
            {
            pelement[wp2]++;
                 Partition[wp2][pelement[wp2]]=G[i].svertex;
            //for(k=1;k<=pelement[wp2];k++)
                //printf(" S= %d ",Partition[wp2][k]);
            //printf("\n");
            i++;
                }
            if(V1==TRUE && V2==TRUE)
            {
            y=(wp1<wp2) ? wp1 :wp2;
            z=(wp1>wp2) ? wp1 :wp2;
            l=pelement[y];
            pelement[y] += pelement[z];
            p=1;
            for(k=l+1;k<=pelement[y];k++)
                {
                Partition[y][k]=Partition[z][p];
                //printf(" %d ",Partition[z][p]);
                p++;
                }
            //for(k=1;k<=pelement[y];k++)
                //printf(" S= %d ",Partition[y][k]);
            //printf("\n");
            for(k=z;k<p_count;k++)
                {
                l=pelement[k+1];
                for(m=1;m<=l;m++)
                    Partition[k][m]=Partition[k+1][m];
                }
            i++;
            p_count--;
                }
            if(i==edge_count)
        break;
        }
    else
        {
        i++;
        if(i==edge_count)
        break;
        }
    }  
    printf("\n The minimum cost is: %f\n",min_cost);
 return;
}
void sort_edges(Graph *G,int edge_count)
{
    int i,j,count=0;;
    float temp;
    for(i=1;i<=edge_count;i++)
        {
            for(j=1;j<=edge_count-i;j++)
                {
                if(G[j].ecost>G[j+1].ecost)
                    {
                    temp=G[j].ecost;
                    G[j].ecost=G[j+1].ecost;
                    G[j+1].ecost=temp;
                    temp=G[j].svertex;
                    G[j].svertex=G[j+1].svertex;
                    G[j+1].svertex=temp;
                    temp=G[j].evertex;
                    G[j].evertex=G[j+1].evertex;
                    G[j+1].evertex=temp;
                    }
                }
        }
    printf("\n");
    return;
}