Kruskal’s Algorithm in C — Minimum Spanning Tree with Union-Find

Kruskal’s algorithm finds the minimum spanning tree (MST) of a weighted, connected, undirected graph — the cheapest possible set of edges that connects every vertex with no cycles. It’s the classic greedy approach: sort all edges by weight, then keep taking the cheapest edge that doesn’t form a cycle. Road networks, electrical wiring, and network cabling problems all reduce to exactly this. This page gives you a complete, tested C implementation using qsort() and a union-find (disjoint set) structure with path compression — the version interviewers actually expect, not the naive matrix scan.

How Kruskal’s Algorithm Works — Step by Step

1. Sort all edges in ascending order of weight.
2. Start with every vertex in its own component (its own set).
3. Walk the sorted edge list. For each edge (u, v): if u and v are in different components, take the edge and merge the two components; if they’re already in the same component, the edge would form a cycle — skip it.
4. Stop when you’ve taken V − 1 edges. That’s the MST.

The “which component is this vertex in?” test is what union-find does: find_root() follows parent links up to a component’s representative, and the union step makes one root point at the other. Path compression flattens the chains as it walks them, keeping lookups nearly O(1).

Example trace (4 vertices, edges sorted: (2,3)=4, (0,3)=5, (0,2)=6, (0,1)=10, (1,3)=15):

Edge	Weight	Components before	Action
(2,3)	4	{0} {1} {2} {3}	Take — merge {2,3}
(0,3)	5	{0} {1} {2,3}	Take — merge {0,2,3}
(0,2)	6	{0,2,3} {1}	Skip — cycle (same set)
(0,1)	10	{0,2,3} {1}	Take — 3 edges = V−1, done

MST weight = 4 + 5 + 10 = 19.

C Program for Kruskal’s Algorithm

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

#define MAX_EDGES 100
#define MAX_VERTICES 20

struct edge {
    int u, v, w;
};

static int parent[MAX_VERTICES];

static int find_root(int i)
{
    while (parent[i] != i) {
        parent[i] = parent[parent[i]];   /* path compression */
        i = parent[i];
    }
    return i;
}

static int compare_edges(const void *a, const void *b)
{
    const struct edge *ea = (const struct edge *)a;
    const struct edge *eb = (const struct edge *)b;
    return ea->w - eb->w;
}

int main(void)
{
    struct edge edges[MAX_EDGES];
    int n, m, i, taken = 0, total = 0;

    printf("Enter the number of vertices: ");
    if (scanf("%d", &n) != 1 || n < 2 || n > MAX_VERTICES) {
        printf("Invalid number of vertices.\n");
        return 1;
    }
    printf("Enter the number of edges: ");
    if (scanf("%d", &m) != 1 || m < 1 || m > MAX_EDGES) {
        printf("Invalid number of edges.\n");
        return 1;
    }
    printf("Enter each edge as: vertex1 vertex2 weight (vertices 0..%d)\n", n - 1);
    for (i = 0; i < m; i++) {
        if (scanf("%d %d %d", &edges[i].u, &edges[i].v, &edges[i].w) != 3 ||
            edges[i].u < 0 || edges[i].u >= n ||
            edges[i].v < 0 || edges[i].v >= n) {
            printf("Invalid edge.\n");
            return 1;
        }
    }

    qsort(edges, (size_t)m, sizeof edges[0], compare_edges);

    for (i = 0; i < n; i++) {
        parent[i] = i;
    }

    printf("\nEdges in the minimum spanning tree:\n");
    for (i = 0; i < m && taken < n - 1; i++) {
        int ru = find_root(edges[i].u);
        int rv = find_root(edges[i].v);

        if (ru != rv) {
            parent[ru] = rv;             /* union the two components */
            printf("  (%d, %d)  weight %d\n", edges[i].u, edges[i].v, edges[i].w);
            total += edges[i].w;
            taken++;
        }
    }

    if (taken != n - 1) {
        printf("The graph is not connected - no spanning tree exists.\n");
        return 1;
    }
    printf("Total weight of the MST: %d\n", total);
    return 0;
}

How to Compile and Run

gcc -ansi -Wall -Wextra -o kruskal kruskal.c
./kruskal

Compiles with zero warnings on GCC and Clang.

Sample Input and Output

Test 1 — the 4-vertex graph traced above:

Enter the number of vertices: 4
Enter the number of edges: 5
Enter each edge as: vertex1 vertex2 weight (vertices 0..3)
0 1 10
0 2 6
0 3 5
1 3 15
2 3 4

Edges in the minimum spanning tree:
  (2, 3)  weight 4
  (0, 3)  weight 5
  (0, 1)  weight 10
Total weight of the MST: 19

Test 2 — 5 vertices, 7 edges:

Enter the number of vertices: 5
Enter the number of edges: 7
Enter each edge as: vertex1 vertex2 weight (vertices 0..4)
0 1 2
0 3 6
1 2 3
1 3 8
1 4 5
2 4 7
3 4 9

Edges in the minimum spanning tree:
  (0, 1)  weight 2
  (1, 2)  weight 3
  (1, 4)  weight 5
  (0, 3)  weight 6
Total weight of the MST: 16

Test 3 — a disconnected graph (two separate pairs) is detected: fewer than V−1 edges get taken, and the program reports The graph is not connected - no spanning tree exists.

Code Explanation

• struct edge — Kruskal works on an edge list, not an adjacency matrix. That’s what makes sorting natural and keeps the memory at O(E).
• compare_edges() — the comparator handed to qsort(); returning ea->w - eb->w sorts ascending by weight.
• find_root() — walks parent links until it reaches a vertex that is its own parent (the component’s representative). The line parent[i] = parent[parent[i]] is path compression: every lookup shortens the chain for the next one.
• parent[ru] = rv — the union: pointing one root at the other merges the two components in O(1).
• taken < n - 1 — the loop stops as soon as the tree is complete; a connected graph’s MST always has exactly V−1 edges, and checking the final count doubles as disconnected-graph detection (the 2012 version of this program looped forever on disconnected input).

Time and Space Complexity

Aspect	Complexity	Why
Sorting edges	O(E log E)	qsort on the edge list — dominates the total
Union-find operations	~O(E α(V)) ≈ O(E)	near-constant per operation with path compression
Total time	O(E log E)
Space	O(E + V)	edge list + parent array

Kruskal vs Prim: Kruskal sorts edges and suits sparse graphs (E close to V); Prim’s algorithm grows one tree from a start vertex and wins on dense graphs, especially with an adjacency matrix. Both produce an MST of identical total weight.

What This Program Teaches

• The greedy-choice property: locally cheapest safe edge → globally minimal tree
• Union-find (disjoint sets) with path compression — a data structure interviewers love on its own
• Using qsort() with a comparator on an array of structs
• Detecting disconnected graphs by counting accepted edges

Related C Programs

• Prim’s Algorithm in C — the other MST algorithm, compared above
• Dijkstra’s Algorithm in C — shortest paths, same greedy family
• Breadth-First Search (BFS) in C
• Depth-First Search (DFS) in C

Test yourself: our free C Programming Quiz app for Android has 150+ questions with explanations for every answer.

Recommended Book

The C Programming Language by Kernighan & Ritchie remains the definitive C reference — we’ve solved all of its exercises. Also on Amazon.com.