Kruskal's Algorithm Implementation in C - MYCPLUS - C and C++ Programming Resources

In this article we show you the implementation of Kruskal’s Algorithm in C Programming Language. This algorithm is directly based on the generic MST (Minimum Spanning Tree) algorithm. A minimum spanning tree is a subgraph of the graph (a tree) with the minimum sum of edge weights.

Kruskal’s algorithm is a greedy algorithm in graph theory that finds a minimum spanning tree for a connected weighted graph. 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.

This algorithm initially appeared in “On the Shortest Spanning Subtree of a Graph and the Traveling Salesman Problem” research paper by Joseph B. Kruskal, Jr. in the proceedings of the American Mathematical Society Vol. 7, No. 1 (Feb., 1956), pp. 48-50.

Kruskal’s algorithm addresses two problems as mentioned below.

PROBLEM 1. Give a practical method for constructing a spanning subtree of minimum length.
PROBLEM 2. Give a practical method for constructing an unbranched spanning subtree of minimum length.

Kruskal’s algorithm is most suitable for sparse graphs (low number of edges). This algorithm is practically used in many fields such as Traveling Salesman Problem, Creating Mazes and Computer Networks etc.

Pseudo code of the Kruskal’s Algorithm

KRUSKAL(V, E, w)

A ← { }           ▷ Set A will ultimately contains the edges of the MST
for each vertex v in V
    do MAKE-SET(v)
sort E into non decreasing order by weight w
for each (u, v) taken from the sorted list
    do if FIND-SET(u) = FIND-SET(v)
        then A ← A ∪ {(u, v)}
            UNION(u, v)
return A

KRUSKAL(V, E, w)

A ← { } ▷ Set A will ultimately contains the edges of the MST

for each vertex v in V

do MAKE-SET(v)

sort E into non decreasing order by weight w

for each (u, v) taken from the sorted list

do if FIND-SET(u) = FIND-SET(v)

then A ← A ∪ {(u, v)}

UNION(u, v)

return A

Complexity of Kruskal’s Algorithm

The time complexity Of Kruskal’s Algorithm is: O(e log v).

Explanation:

Kruskal’s algorithm takes o(e log e) time in sorting of the edges. Here e is numbers of edges and v is the number of vertices in the graph. Further, it iterates all edges and runs a subroutine to find the cycles in the graph which is called union-find algorithm. The union-find algorithm requires o(log v) time and is applied after sorting of edges is completed.

So, Overall Kruskal’s algorithm requires o(e log v) time to run.

C Programming Implementation of Kruskal’s Algorithm

Here is the C program that implements this algorithm.

    #include &lt;stdio.h&gt;
    #include &lt;conio.h&gt;
    #include &lt;stdlib.h&gt;

    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);
    void main() {
      printf("\n\tImplementation of Kruskal's Algorithm\n");
      printf("\nEnter the no. of vertices:");
      scanf("%d", &amp; n);
      printf("\nEnter the cost adjacency matrix:\n");
      for (i = 1; i &lt;= n; i++) {
        for (j = 1; j &lt;= n; j++) {
          scanf("%d", &amp; cost[i][j]);
          if (cost[i][j] == 0)
            cost[i][j] = 999;
        }
      }
      printf("The edges of Minimum Cost Spanning Tree are\n");
      while (ne &lt; n) {
        for (i = 1, min = 999; i &lt;= n; i++) {
          for (j = 1; j &lt;= n; j++) {
            if (cost[i][j] &lt; 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] = cost[b][a] = 999;
      }
      printf("\n\tMinimum cost = %d\n", mincost);
      getch();
    }
    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;
    }

#include <stdio.h>

#include <conio.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);

void 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] = cost[b][a] = 999;

}

printf("\n\tMinimum cost = %d\n", mincost);

getch();

}

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;

}

Output of the C Program

   Implementation of Kruskal's Algorithm
 
Enter the no. of vertices:3  
 
Enter the cost adjacency matrix: 
9
8
7
6
5
4
3
2
3
The edges of Minimum Cost Spanning Tree are  
1 edge (3,2) =2  
2 edge (3,1) =3  
 
Minimum cost = 5