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.

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

1 2 3 4 5 6 7 8 9 10 11 | 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.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 | #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

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 | 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 |