Write a C Program to Construct the Minimum Spanning Tree Using the Kruskal’s Algorithm

by

Aim:

To construct the minimum spanning tree using Kruskal’s Algorithm.

Theory:

  • Given a connected and undirected graph, a spanning tree of that graph is a subgraph that is a tree and connects all the vertices together.
  • A single graph can have many different spanning trees.
  • A minimum spanning tree (MST) or minimum weight spanning tree for a weighted, connected and undirected graph is a spanning tree with weight less than or equal to the weight of every other spanning tree.
  • The weight of a spanning tree is the sum of weights given to each edge of the spanning tree.

Kruskal’s Algorithm

  • Kruskal’s Algorithm builds the spanning tree by adding edges one by one into a growing spanning tree.
  • Kruskal’s algorithm follows greedy approach as in each iteration it finds an edge which has least weight and adds it to the growing spanning tree.

Algorithm:

  • Sort the graph edges with respect to their weights.
  • Start adding edges to the MST from the edge with the smallest weight until the edge of the largest weight.
  • Only add edges which doesn’t form a cycle, edges which connect only disconnected components.

In Kruskal’s algorithm, at each iteration, we will select the edge with the lowest weight. So, we will start with the lowest weighted edge first i.e., the edges with weight 1. After that, we will select the second-lowest weighted edge i.e., edge with weight 2. Notice these two edges are totally disjoint. Now, the next edge will be the third-lowest weighted edge i.e., edge with weight 3, which connects the two disjoint pieces of the graph. Now, we are not allowed to pick the edge with weight 4, which will create a cycle and we can’t have any cycles. So we will select the fifth-lowest weighted edge i.e., edge with weight 5. Now the other two edges will create cycles so we will ignore them. In the end, we end up with a minimum spanning tree with total cost 11 ( = 1 + 2 + 3 + 5).

Program:

#include<stdio.h>
#define MAX 30
typedef struct edge
{
int u,v,w;
}edge;
 
typedef struct edgelist
{
edge data[MAX];
int n;
}edgelist;
 
edgelist elist;
 
int G[MAX][MAX],n;
edgelist spanlist;
 
void kruskal();
int find(int belongs[],int vertexno);
void union1(int belongs[],int c1,int c2);
void sort();
void print();
 
void main()
{
int i,j,total_cost;
printf("\nEnter number of vertices:");
scanf("%d",&n);
printf("\nEnter the adjacency matrix:\n");
for(i=0;i<n;i++)
for(j=0;j<n;j++)
scanf("%d",&G[i][j]);
kruskal();
print();
}
 
void kruskal()
{
int belongs[MAX],i,j,cno1,cno2;
elist.n=0;
 
for(i=1;i<n;i++)
for(j=0;j<i;j++)
{
if(G[i][j]!=0)
{
elist.data[elist.n].u=i;
elist.data[elist.n].v=j;
elist.data[elist.n].w=G[i][j];
elist.n++;
}
}
sort();
for(i=0;i<n;i++)
belongs[i]=i;
spanlist.n=0;
for(i=0;i<elist.n;i++)
{
cno1=find(belongs,elist.data[i].u);
cno2=find(belongs,elist.data[i].v);
if(cno1!=cno2)
{
spanlist.data[spanlist.n]=elist.data[i];
spanlist.n=spanlist.n+1;
union1(belongs,cno1,cno2);
}
}
}
 
int find(int belongs[],int vertexno)
{
return(belongs[vertexno]);
}
 
void union1(int belongs[],int c1,int c2)
{
int i;
for(i=0;i<n;i++)
if(belongs[i]==c2)
belongs[i]=c1;
}
 
void sort()
{
int i,j;
edge temp;
for(i=1;i<elist.n;i++)
for(j=0;j<elist.n-1;j++)
if(elist.data[j].w>elist.data[j+1].w)
{
temp=elist.data[j];
elist.data[j]=elist.data[j+1];
elist.data[j+1]=temp;
}
}
 
void print()
{
int i,cost=0;
for(i=0;i<spanlist.n;i++)
{
printf("\n%d\t%d\t%d",spanlist.data[i].u,spanlist.data[i].v,spanlist.data[i].w);
cost=cost+spanlist.data[i].w;
}
printf("\n\nCost of the spanning tree=%d",cost);
}

Execution:

Input:
5 1 5 2 8 6 0 4 7 5 1 9 6 4 7 0 6 3 0 6 1 7 5 3 6 0

Output:

Enter number of vertices:
Enter the adjacency matrix:

3	1	3
4	2	3
4	1	5
3	0	6

Cost of the spanning tree=17

Result:

Thus construct the minimum spanning tree using Kruskal Algorithm was executed successfully.

Leave a Comment