Kruskal's Algorithm in C

Tweet

        /* Program to implement Kruskal's Algorithm */
      
    #include<stdio.h>  
    #include<stdlib.h>       
    void makeset();  
    void graph(int);  
    void kruskal();  
    struct node *findset(struct node *);  
    void union1(struct node *,struct node *);  
      
    int j=0;  
    struct node //Declare the structure of a node  
    {  
        int data,rank;  
        struct node *next,*parent;  
    };       
    struct edge //Declare the structure of a edge  
    {  
        int len;  
        struct node *src,*destination;  
    };        
    struct node *head[10];  
    struct edge *e[40];       
    int main()  
    {  
        int n,i;  
        printf("\nEnter no.of vertices in the graph : ");  
        scanf("%d",&n);  
        for(i=1;i<=n;i++)  
        {  
            makeset(i); //initialise each vertex  
        }  
        graph(n);  
        kruskal();      
    }      
    void makeset(int a)  
    {  
        struct node *x;  
        x=(struct node*)malloc(sizeof(struct node));  
        x->data=a;  
        x->parent=x;  
        x->rank=0;  
        x->next=NULL;  
        head[a]=x;  
    }     
    void graph(int n)   //here input neighbours of each vertex & the weight of edges  
    {  
        int i,k,l,len;  
        int dest;  
        for(i=1;i<=n;i++)  
        {  
            printf("\nfor vertex %d Enter no. of edges ",i);  
            scanf("%d",&l);  
            for(k=1;k<=l;k++)  
            {  
            printf("Enter destination vertex for %dth edge for vertex %d ",k,i);  
            scanf("%d",&dest);  
            j++;  
            e[j]=(struct edge*)malloc(sizeof(struct edge));  
            e[j]->src=head[i];  
            e[j]->destination=head[dest];  
            printf("Enter length of edge : ");  
            scanf("%d",&len);  
            e[j]->len=len;  
            }  
        }  
    }      
    void kruskal()  //Apply actual concept of kruskal  
    {  
        int i,k,l,p;  
        struct edge *temp;  
        i=1;  
        while(i<j)   //sort the edges with increasing order of their weights  
        {       //using insertion sort  
            p=i;  
            k=i+1;  
            while(k<=j)  
            {  
                if(e[p]->len>e[k]->len)  
                {  
                    p=k;  
                }  
                k++;  
            }  
            if(p!=i)  
            {  
            temp=e[p];  
            e[p]=e[i];  
            e[i]=temp;  
            }  
            i++;  
        }  
        printf("\nMST includes the following edges that are :\n");  
        for(i=1;i<=j;i++)  
        {  
            if(findset(e[i]->src)!=findset(e[i]->destination))    //if representative  
            {                           //of src & dest. are different  
            union1((findset(e[i]->src)),(findset(e[i]->destination)));    //then make connection  
            printf("\n%d->%d",e[i]->src->data,e[i]->destination->data);  //b/w them  
            }  
        }  
    }       
    struct node *findset(struct node *a)    //return the represenative of node  
    {  
        if(a!=a->parent)  
        {  
            a->parent=findset(a->parent);  
        }  
        return a->parent;  
    }      
    void union1(struct node *x,struct node *y)  //join the two vertex if desired  
    {  
        if(x->rank>y->rank)  
            y->parent=x;  
        else  
            x->parent=y;  
        if(x->rank==y->rank)  
        y->rank=y->rank+1;  
    }  

Posted in: Algorithms , Graphs , Linked List in C , Programming in C , Tree