Kruskal Algorithm in C

Here is another important graph algo for finding the minimum weighted spanning tree imlimented in C.Input is taken from adj matrix with non-conn terms having val in #define MAXVAL & the number of vert changed by changing #define MAXVAL...


/*KRUSKAL ALGORITHM IN C*/
#include<stdio.h>
#define VERT 4 //predefined number of vertices
#define MAXVAL 99
void kruskal(int a[][VERT],int n);
int gethead(int vert,int par[]);
void vertex_union(int v1,int v2,int par[]);

void vertex_union(int v1,int v2,int par[])
{
    if(v1>v2)
    par[v1]=v2;
    else
    par[v2]=v1;
}

int gethead(int vert,int par[])
{
    while(par[vert]!=vert)
    {
        vert=par[vert];
    }
    return vert;
}

void kruskal(int a[][VERT],int n)
{
    int nofedges,i,parent[VERT],min,j,k,u,v,path[VERT-1][2],sum;
    nofedges=k=sum=0;
    for(i=0;i<n;i++)
    parent[i]=i;//sets parent
    while(nofedges<n-1)
    {
        min=MAXVAL;
        for(i=0;i<n;i++)
        for(j=0;j<n;j++)
        if(a[i][j]<min)
        {
            min=a[i][j];
            u=i;
            v=j;
        }//gets the min for each turn
        if(min!=MAXVAL)
        {
            i=gethead(u,parent);
            j=gethead(v,parent);
            /*printf("==>%d %d %d %d\n",i,j,u,v);
            int ii;
            for(ii=0;ii<VERT;ii++)
            printf("%d ",parent[ii]);
            printf("\n");*/
            if(i!=j)
            {
                //printf("-->adding vertex %d %d",u,v);
                path[k][0]=u;
                path[k][1]=v;
                k++;
                sum+=min;
                vertex_union(i,j,parent);
                nofedges+=1;
            }
            a[u][v]=a[v][u]=999;
        }
    }
    if(nofedges!=n-1)
    printf("Invalid Spanning Tree");
    else
    {
        printf("Minimum cost=%d\n",sum);
        printf("The edges included are ::\n");
        for(i=0;i<n-1;i++)
        printf("%d %d \n",path[i][0],path[i][1]);
    }
}

int main()
{
    int cost[VERT][VERT],i,j;
    for(i=0;i<VERT;i++)
    for(j=0;j<VERT;j++)
    scanf("%d",&cost[i][j]);
    //adjacency matrix entered
    kruskal(cost,VERT);

}

Hope you enjoyed this..