Minimum Spanning Tree using Kruskal's Algorithm

In this method, first, we examine all the edges one by one starting from the smallest edge. To decide whether the selected edge should be included in the spanning tree or not, we will examine the nodes connecting the edge. If the two belong to the same tree then we will not include the edge in the spanning tree, since the two nodes are in the same tree, they are already connected, and adding these edges would result in a cycle. So we will insert an edge in the spanning tree only if its nodes are in different trees.

How can we decide whether two nodes are in the same tree or not?

This can be done through UNION-FIND structure which is based on the partition of a set. A partition of a set may be thought of as a set of equivalence classes. Each subset of the partition contains a set of equivalent elements. For each subset, we denote one element as the representative of that subset. Each element in the subset is, somehow, equivalent and represented by the representative. When we add elements to the subset, we arrange that all the elements point to their representative. Initially, each node is its own representative. As the initial pair of nodes are joined to form a tree, the representative pointer of one of the nodes is made to point to the other, which becomes the representative of the tree. Let x denote an object, we wish to support the following operations.

1.MAKE-SET(x)creates a new set whose only member is pointed to by x.
2.FIND-SET(x)returns a pointer to the representative of the set containing x.
3.UNION(x,y)unites the dynamic sets that contain x and y, say Sx and Sy
  into a new set that is the union of these two sets. The representative of the 
  resulting set is some member of Sx⋃Sy. Since we require 
  the sets in the collection to be disjoint, we destroy the sets Sx and Sy 
  removing them from the collection.				

Let's now see the procedure of the Kruskal algorithm.

Kruskal's Algorithm

MST-KRUSKAL(G,w)
A<-φ
for each vertex v &Belongs;V[G] do
     MAKE-SET(v)
sort the edges of E into increasing order by weight w.
for each edge (u,v)&belongsto;E taken in increasing order do
      if FIND-SET(u)!= FIND-SET(v) then
           A<-A ⋃ {u,v}
           UNION (u,v)
return A                 

Let's take an example.

#include<stdio.h> #include<stdlib.h> #include<limits.h> int find(int i, int *parent) { while(parent[i]) i = parent[i]; return i; } int myunion(int i, int j, int *parent) { if(i != j) { parent[j] = i; return 1; } return 0; } void kruskal(int size, int **adjMat, int *parent, int minCost, int chk){ int min = 0, r = 0, c = 0, i = 0, j = 0; while(chk <= size){ for(i = 1, min = INT_MAX; i <= size; i++){ for(j = 1; j <= size; j++){ if(min > adjMat[i][j] && adjMat[i][j] != 0){ min = adjMat[i][j]; r = i; c = j; } } } if(myunion(find(r, parent),find(c, parent), parent)){ minCost += adjMat[r][c]; } adjMat[r][c] = adjMat[c][r] = INT_MAX; chk++; } printf("%d", minCost); } int main(){ int size, minCost = 0, chk = 1, **adjMat, *parent, i = 0, j = 0; scanf("%d", &size); parent = (int *)malloc((size + 1) * sizeof(int)); adjMat = (int **)malloc((size + 1)*sizeof(int *)); for(i = 0; i <= size; i++) adjMat[i] = (int *)malloc((size + 1) * sizeof(int)); for(i = 0; i <= size; i++) parent[i] = 0; for(i = 1; i <= size; i++){ for(j = 1; j <= size; j++){ scanf("%d", &adjMat[i][j]); if(adjMat[i][j] == 0){ adjMat[i][j] = INT_MAX; } } } kruskal(size, adjMat, parent, minCost, chk); return 0; }

Happy Exploring!