I have this code my professor gave me about finding MST's using Kruskal's Algorithm. However, I do not understand exactly what the need for
int parent[10]
is and what is happening when we are using the functions
find()
and
uni()
Below is the full code that he gave us.
#include <stdio.h>
int parent[10];
int find(int i)
{
while(parent[i])
{
i=parent[i];
}
return i;
}
int uni(int i,int j)
{
if(i!=j)
{
parent[j]=i;
return 1;
}
return 0;
}
int main(void)
{
int cost[10][10],u,v,i,j,min,mincost=0,n,ne=1,a,b;
printf("Enter no. of vertices: ");
scanf("%d",&n);
printf("Enter Adjacency Matrix:\n");
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
scanf("%d",&cost[i][j]);
}
}
while(ne<n)
{
min=999;
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
if(cost[i][j]<min)
{
min=cost[i][j];
a=u=i;
b=v=j;
}
}
}
u=find(u);
v=find(v);
if(uni(u,v))
{
printf("\n%d edge(%d -> %d)=%d",ne++,a,b,min);
mincost += min;
}
cost[a][b]=cost[b][a]=999;
}
printf("\nMin. cost of spanning tree=%d",mincost);
return 0;
}
I am just looking for an explination of the three things that I stated above. I understand how the algorithm works except for the three things that I stated.
Thank you
This code supports a maximum of 10 vertices.
parent
is keeping track of the parent of the node.find
is used for finding the vertex in a set (say A) which does not have any parent.
So if u is in set A and v is in set B, the two sets are being unioned by uni
function.This code works but it is not how you code.
About the algorithm itself:
Kruskal is a greedy algorithm for finding the minimum spanning tree with the least (or maximum cost). The algorithm is as follows:
uv
check if u
and v
belong to the same set. If yes do nothing repeat from step 2.u
and v
are present i.e if u is in set A and v in set B union A and B as C and discard A and B. Now u
and v
belong to C. Repeat from step 2.Here is a better code : https://github.com/26prajval98/DSA/blob/master/graph%20algorithms/kruskal/main.c