How does this code for Kruskal's MST algorithm work?

Question

Below is the C++ code for Kruskal's algorithm for finding the minimum cost spanning tree of a graph given by my instructor.

I did not understand the code well. I want to know exactly what part of the code is checking for formation of a cycle in the growing forest of included edges.

I also want to know that what exactly is the purpose of the parent[] array.

Also, is it a better way than checking for cycles using DFS (depth first search)?

Here is the code:

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

int i, j, k, a, b, u, v, n, ne = 1;
int min, mincost = 0, cost[9][9], parent[9];

int find(int);
int uni(int, int);

int main()
{
    printf("\n\tImplementation of Kruskal's algorithm\n");
    printf("\nEnter the no. of vertices:");
    scanf("%d",&n);
    printf("\nEnter the cost adjacency matrix:\n");

    for (i = 1; i <= n; i++)
    {
        for(j = 1; j <= n; j++)
        {
            scanf("%d",&cost[i][j]);
            if(cost[i][j] == 0)
                cost[i][j] = 999;
        }
    }

    printf("The edges of Minimum Cost Spanning Tree are\n");

    while(ne < n)
    {
        for(i = 1, min = 999; 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("%d edge (%d, %d) =%d\n", ne++, a, b, min);
            mincost += min;
        }
        cost[a][b] = 999;
    }
    printf("\n\tMinimum cost = %d\n",mincost);
}

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;
}

Note:

I am aware that the code is messed up a bit and user input will result in failure in case the user enters a value more than 9, but I don't want to focus on that part without understanding how it works. I just know that it selects the minimum cost edge, checks it for the formation of the cycle and then sets its value to infinity (here 999). I don't know how and where it is checking for cycle formation. Please help by explaining.

Answer 1

The code inside the while loop in main finds the lightest edge that has not yet been considered. That edge is between nodes u and v. The edge can form a cycle only if u and v already belong to the same tree.

This:

u=find(u);
v=find(v);

finds the roots of the trees to which u and v belong. Then main passes those two roots to uni:

if(uni(u,v))
  ...

int uni(int i,int j)
  {
    if(i!=j)
      {
        parent[j]=i;
        return 1;
      }
    return 0;
  }

If the two roots are the same, the code does nothing, the edge is not used.