C program to Find Minimum Spanning tree KRUSKAL’s Algorithm

# C program to Find Minimum Spanning tree KRUSKAL’s Algorithm

2767
1
SHARE

C program to Find KRUSKAL’s Algorithm : Kruskal’s algorithm is a greedy algorithm in graph theory that finds a minimum spanning tree for a connected weighted graph. 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).

Generalized approach to find Minimum Spanning tree of weighted graphs using KRUSKAL’s Algorithm :

• create a forest F (a set of trees), where each vertex in the graph is a separate tree

• create a set S containing all the edges in the graph

• while S is nonempty and F is not yet spanning

• remove an edge with minimum weight from S

• if that edge connects two different trees, then add it to the forest, combining two trees into a single tree

At the termination of the algorithm, the forest forms a minimum spanning forest of the graph. If the graph is connected, the forest has a single component and forms a minimum spanning tree.

Lets see how to write a C code to implement KRUSKAL’s Algorithm to find Minimum Spanning tree of weighted graphs.

# C program to Find Minimum Spanning tree using KRUSKAL’s Algorithm  :

```#include<stdio.h>
#define INF 1000
char vertex[10];
int wght[10][10];
int span_wght[10][10];
int source;
struct Sort
{
int v1,v2;
int weight;
}que[20];
int n,ed,f,r;
int cycle(int s,int d)
{
int j,k;
if(source==d)
return 1;
for(j=0;j<n;j++)
if(span_wght[d][j]!=INF && s!=j)
{
if(cycle(d,j))
return 1;
}
return 0;
}
void build_tree()
{
int i,j,w,k,count=0;
for(count=0;count<n;f++)
{
i=que[f].v1;
j=que[f].v2;
w=que[f].weight;
span_wght[i][j]=span_wght[j][i]=w;
source=i;
k=cycle(i,j);
if(k)
span_wght[i][j]=span_wght[j][i]=INF;
else
count++;
}
}
void swap(int *i,int *j)
{
int t;
t=*i;
*i=*j;
*j=t;
}
void main()
{
int i,j,k=0,temp;
int sum=0;
clrscr();
printf("\n\n\tKRUSKAL'S ALGORITHM TO FIND SPANNING TREE\n\n");
printf("\n\tEnter the No. of Nodes : ");
scanf("%d",&n);
for(i=0;i<n;i++)
{
printf("\n\tEnter %d value : ",i+1);
fflush(stdin);
scanf("%c",&vertex[i]);
for(j=0;j<n;j++)
{
wght[i][j]=INF;
span_wght[i][j]=INF;
}
}
printf("\n\nGetting Weight\n");
for(i=0;i<n;i++)
for(j=i+1;j<n;j++)
{
printf("\nEnter 0 if path Doesn't exist between %c to %c : ",vertex[i],vertex[j]);
scanf("%d",&ed);
if(ed>=1)
{
wght[i][j]=wght[j][i]=ed;
que[r].v1=i;
que[r].v2=j;
que[r].weight=wght[i][j];
if(r)
{
for(k=0;k<r;k++)
if(que[k].weight>que[r].weight)
{
swap(&que[k].weight,&que[r].weight);
swap(&que[k].v1,&que[r].v1);
swap(&que[k].v2,&que[r].v2);
}
}
r++;
}
}
clrscr();
printf("\n\tORIGINAL GRAPH WEIGHT MATRIX\n\n");
printf("\n\tweight matrix\n\n\t");
for(i=0;i<n;i++,printf("\n\t"))
for(j=0;j<n;j++,printf("\t"))
printf("%d",wght[i][j]);
build_tree();
printf("\n\n\t\tMINIMUM SPANNING TREE\n\n");
printf("\n\t\tLIST OF EDGES\n\n");
for(i=0;i<n;i++)
for(j=i+1;j<n;j++)
if(span_wght[i][j]!=INF)
{
printf("\n\t\t%c ------ %c = %d ",vertex[i],vertex[j],span_wght[i][j]);
sum+=span_wght[i][j];
}
printf("\n\n\t\tTotal Weight : %d ",sum);
getch();
}```

We hope you all have enjoyed the of Kruskal’s Algorithm to find minimum spanning tree. If you have any doubts or queries ask us in form of comments.

SHARE
Previous articleC program to find Minimum Spanning tree PRIM’s Algorithm
Well, I am software programmer and love to code. My hobbies is to do Hacking, Coding, Blogging, Web Designing and playing online games. Feel free to contact me at shiviskingg@gmail.com or lokesh@hackingloops.com