C Program for Minimum Spanning Tree using Kruskal’s Algorithm Example

By | 11.07.2017

Minimum Spanning Tree using Kruskal’s Algorithm


Write a C Program for Creating Minimum Spanning Tree using Kruskal’s Algorithm Example. Here’s simple Program for creating minimum cost spanning tree using kruskal’s algorithm example in C Programming Language.


Kruskal’s Algorithm


Kruskal’s algorithm is a minimum-spanning-tree algorithm which finds an edge of the least possible weight that connects any two trees in the forest.

It is a greedy algorithm in graph theory as it finds a minimum spanning tree for a connected weighted graph adding increasing cost arcs at each step.

This means it finds a subset of the edges that forms a tree that includes every vertex, where the total weight of all the edges in the tree is minimized.

If the graph is not connected, then it finds a minimum spanning forest (a minimum spanning tree for each connected component).


Also Read : : C Program for Creating Minimum Spanning Tree using Prim’s Algorithm

Below is the source code for C Program for Minimum Spanning Tree using Kruskal’s Algorithm Example which is successfully compiled and run on Windows System to produce desired output as shown below :


SOURCE CODE : :


/*  C Program for Minimum Spanning Tree using Kruskal's Algorithm Example */

#include<stdio.h>
#include<stdlib.h>

#define MAX 100
#define NIL -1

struct edge
{
        int u;
        int v;
        int weight;
        struct edge *link;
}*front = NULL;

void make_tree(struct edge tree[]);
void insert_pque(int i,int j,int wt);
struct edge *del_pque();
int isEmpty_pque( );
void create_graph();

int n;   /*Total number of vertices in the graph */

int main()
{
        int i;
        struct edge tree[MAX]; /* Will contain the edges of spanning tree */
        int wt_tree = 0; /* Weight of the spanning tree */

        create_graph();

        make_tree(tree);

        printf("\nEdges to be included in minimum spanning tree are :\n");
        for(i=1; i<=n-1; i++)
        {
                printf("\n%d->",tree[i].u);
                printf("%d\n",tree[i].v);
                wt_tree += tree[i].weight;
        }
        printf("\nWeight of this minimum spanning tree is : %d\n", wt_tree);

        return 0;

}/*End of main()*/

void make_tree(struct edge tree[])
{
        struct edge *tmp;
        int v1,v2,root_v1,root_v2;
        int father[MAX]; /*Holds father of each vertex */
        int i,count = 0;    /* Denotes number of edges included in the tree */

        for(i=0; i<n; i++)
                father[i] = NIL;

        /*Loop till queue becomes empty or
        till n-1 edges have been inserted in the tree*/
        while( !isEmpty_pque( ) && count < n-1 )
        {
                tmp = del_pque();
                v1 = tmp->u;
                v2 = tmp->v;

                while( v1 !=NIL )
                {
                        root_v1 = v1;
                        v1 = father[v1];
                }
                while( v2 != NIL  )
                {
                        root_v2 = v2;
                        v2 = father[v2];
                }

                if( root_v1 != root_v2 )/*Insert the edge (v1, v2)*/
                {
                    count++;
                        tree[count].u = tmp->u;
                        tree[count].v = tmp->v;
                        tree[count].weight = tmp->weight;
                        father[root_v2]=root_v1;
                }
        }

        if(count < n-1)
        {
                printf("\nGraph is not connected, no spanning tree possible\n");
                exit(1);
        }

}/*End of make_tree()*/

/*Inserting edges in the linked priority queue */
void insert_pque(int i,int j,int wt)
{
        struct edge *tmp,*q;

        tmp = (struct edge *)malloc(sizeof(struct edge));
        tmp->u = i;
        tmp->v = j;
        tmp->weight = wt;

        /*Queue is empty or edge to be added has weight less than first edge*/
        if( front == NULL || tmp->weight < front->weight )
        {
                tmp->link = front;
                front = tmp;
        }
        else
        {
                q = front;
                while( q->link != NULL && q->link->weight <= tmp->weight )
                        q = q->link;
                tmp->link = q->link;
                q->link = tmp;
                if(q->link == NULL)  /*Edge to be added at the end*/
                        tmp->link = NULL;
        }
}/*End of insert_pque()*/

/*Deleting an edge from the linked priority queue*/
struct edge *del_pque()
{
        struct edge *tmp;
        tmp = front;
        front = front->link;
        return tmp;
}/*End of del_pque()*/

int isEmpty_pque( )
{
        if ( front == NULL )
                return 1;
        else
                return 0;
}/*End of isEmpty_pque()*/

void create_graph()
{
        int i,wt,max_edges,origin,destin;

        printf("\nEnter number of vertices : ");
        scanf("%d",&n);
        max_edges = n*(n-1)/2;

        for(i=1; i<=max_edges; i++)
        {
                printf("\nEnter edge %d(-1 -1 to quit): ",i);
                scanf("%d %d",&origin,&destin);
                if( (origin == -1) && (destin == -1) )
                        break;
                printf("\nEnter weight for this edge : ");
                scanf("%d",&wt);
                if( origin >= n || destin >= n || origin<0 || destin<0)
                {
                        printf("\nInvalid edge!\n");
                        i--;
                }
                else
                        insert_pque(origin,destin,wt);
        }
}

OUTPUT : :


/*  C Program for Minimum Spanning Tree using Kruskal's Algorithm Example */

Enter number of vertices : 6

Enter edge 1(-1 -1 to quit): 0 1

Enter weight for this edge : 2

Enter edge 2(-1 -1 to quit): 0 2

Enter weight for this edge : 3

Enter edge 3(-1 -1 to quit): 0 3

Enter weight for this edge : 1

Enter edge 4(-1 -1 to quit): 2 4

Enter weight for this edge : 2

Enter edge 5(-1 -1 to quit): 2 5

Enter weight for this edge : 5

Enter edge 6(-1 -1 to quit): 1 5

Enter weight for this edge : 3

Enter edge 7(-1 -1 to quit): 1 4

Enter weight for this edge : 1

Enter edge 8(-1 -1 to quit): 3 5

Enter weight for this edge : 2

Enter edge 9(-1 -1 to quit): 4 2

Enter weight for this edge : 1

Enter edge 10(-1 -1 to quit): 5 2

Enter weight for this edge : 1

Enter edge 11(-1 -1 to quit): 1 3

Enter weight for this edge : 2

Enter edge 12(-1 -1 to quit): -1 -1

Edges to be included in minimum spanning tree are :

0->3

1->4

4->2

5->2

0->1

Weight of this minimum spanning tree is : 6

Process returned 0

If you found any error or any queries related to the above program or any questions or reviews , you wanna to ask from us ,you may Contact Us through our contact Page or you can also comment below in the comment section.We will try our best to reach up to you in short interval.


Thanks for reading the post…


Recommended Posts : :

4.7 3 votes
Article Rating
Subscribe
Notify of
guest

2 Comments
Oldest
Newest Most Voted
Inline Feedbacks
View all comments
Jhamal

what’s the purpose of int u?

bhojubha sarvaiya

gnyntfh