Kruskal’s Algorithm in C and C++ (Minimum Spanning Tree)

Most Kruskal’s algorithm tutorials have one of two problems: code that doesn’t compile, or a “union-find” that is quietly a linear search. This guide has neither — one example graph runs through the theory, the trace, and three working programs, so you can check every claim against an output.

In this guide you’ll see exactly how the algorithm works on a real graph, why union-find with path compression matters, and complete implementations in C, C++, and Python — all built on the same example graph so you can follow one trace from start to finish. Every program was compiled and run for this update: the C version with gcc -Wall -Wextra under both -std=c11 and -std=c17 (zero warnings, and a clean AddressSanitizer run), the C++ version with g++ -std=c++17 -Wall -Wextra (zero warnings), and the Python version under Python 3.12. Every output block is captured verbatim from those runs.

Table of Contents

• What Is Kruskal's Algorithm?
• Key Concepts
• How Kruskal's Algorithm Works
• Worked Example, Step by Step
• Pseudocode
• Union-Find: The Data Structure That Makes It Fast
• Kruskal's Algorithm in C
• Kruskal's Algorithm in C++
• Kruskal's Algorithm in Python
• Time and Space Complexity
• Kruskal vs Prim: Which One Should You Use?
• Real-World Applications
• Key Takeaways
• Frequently Asked Questions
• Conclusion

What Is Kruskal’s Algorithm?

Kruskal’s algorithm is a greedy algorithm that finds a minimum spanning tree (MST) of a connected, weighted, undirected graph — the set of V − 1 edges that connects every vertex at the lowest possible total weight. It sorts all edges by weight, then accepts each edge in order unless it would create a cycle, detecting cycles with a union-find data structure.

Because it needs only an edge list and a sort, Kruskal’s is usually the simplest MST algorithm to implement correctly — and the union-find structure it depends on is a reusable tool in its own right.

Kruskal’s algorithm was published by Joseph B. Kruskal in “On the Shortest Spanning Subtree of a Graph and the Traveling Salesman Problem”, Proceedings of the American Mathematical Society, Vol. 7, No. 1 (1956).

Key Concepts

• Weighted graph — a set of vertices connected by edges, where each edge carries a numeric weight (cost, distance, latency).
• Spanning tree — a subgraph that connects all V vertices using exactly V − 1 edges and contains no cycles.
• Minimum spanning tree (MST) — the spanning tree whose total edge weight is as small as possible. If all edge weights are distinct, the MST is unique.
• Union-find (disjoint set union, DSU) — a data structure that tracks which vertices belong to the same connected component, with two operations: find (which set is this vertex in?) and union (merge two sets).

Kruskal’s algorithm shines on sparse graphs (few edges relative to vertices), and because it only needs an edge list — not an adjacency structure — it’s often the simplest MST algorithm to implement correctly.

How Kruskal’s Algorithm Works

1. Sort all edges by weight in non-decreasing order.
2. Initialize a union-find structure where every vertex is its own set (a forest of single-vertex trees).
3. Process each edge(u, v) in sorted order:
   • If u and v are in different sets, the edge connects two separate components — add it to the MST and union the sets.
   • If they’re in the same set, the edge would create a cycle — discard it.
4. Stop when the MST contains V − 1 edges.

If you run out of edges before reaching V − 1, the graph isn’t connected and no spanning tree exists (you get a minimum spanning forest instead).

Worked Example, Step by Step

We’ll use this 7-vertex, 11-edge graph in every code example below (vertices A–G):

After sorting the edges, Kruskal’s algorithm processes them like this:

MST edges: A–D, C–E, D–F, A–B, B–E, E–G · Total weight: 39

Every implementation below prints exactly this result.

Pseudocode

Kruskal(vertices V, edges E):
    sort E by weight, ascending
    make-set(v) for every v in V          // union-find: each vertex alone
    MST = {}

    for each edge (u, v, w) in E:
        if find(u) != find(v):            // different components?
            MST = MST ∪ {(u, v, w)}
            union(u, v)
        if |MST| == |V| - 1:
            break

    return MST

Union-Find: The Data Structure That Makes It Fast

The naive way to detect cycles — searching the partial MST for a path between u and v — would make Kruskal’s algorithm quadratic. Union-find does it in effectively constant time using two optimizations:

• Path compression — while finding a vertex’s root, repoint each visited node closer to the root, flattening the tree for future lookups.
• Union by rank — when merging two sets, attach the shorter tree under the taller one, so trees stay shallow.

With both optimizations, a sequence of operations runs in O(α(V)) amortized time per operation — a bound proved by Robert Tarjan in 1975 — where α is the inverse Ackermann function, below 5 for any input that fits in a physical computer. In other words: effectively constant.

This is the part of the implementation interviewers actually probe, so both the C and C++ versions below implement it explicitly rather than hiding it.

Kruskal’s Algorithm in C

This is a complete, standard C17 program — no compiler-specific headers, no fixed-size matrices. Sorting is delegated to the standard library’s qsort rather than a hand-rolled loop, and the program compiles cleanly with gcc -std=c17 -Wall -Wextra.

/* Kruskal's Algorithm in C (C17)
 * Builds a minimum spanning tree from an edge list using
 * union-find with path compression and union by rank.
 * Compile: gcc -std=c17 -Wall -Wextra -O2 kruskal.c -o kruskal
 */
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>

typedef struct {
    int src;
    int dest;
    int weight;
} Edge;

/* ---- Union-Find (Disjoint Set Union) ---- */

typedef struct {
    int *parent;
    int *rank;
} DisjointSet;

static bool ds_init(DisjointSet *ds, int n) {
    ds->parent = malloc((size_t)n * sizeof *ds->parent);
    ds->rank   = calloc((size_t)n, sizeof *ds->rank);
    if (!ds->parent || !ds->rank) {
        free(ds->parent);
        free(ds->rank);
        return false;
    }
    for (int i = 0; i < n; i++)
        ds->parent[i] = i;          /* every vertex starts as its own set */
    return true;
}

static void ds_free(DisjointSet *ds) {
    free(ds->parent);
    free(ds->rank);
}

/* Find the set representative, flattening the path as we go. */
static int ds_find(DisjointSet *ds, int x) {
    while (ds->parent[x] != x) {
        ds->parent[x] = ds->parent[ds->parent[x]];  /* path compression */
        x = ds->parent[x];
    }
    return x;
}

/* Merge the sets containing x and y.
 * Returns false if they were already in the same set
 * (the edge would form a cycle). */
static bool ds_union(DisjointSet *ds, int x, int y) {
    int rx = ds_find(ds, x);
    int ry = ds_find(ds, y);
    if (rx == ry)
        return false;

    /* union by rank: attach the shorter tree under the taller one */
    if (ds->rank[rx] < ds->rank[ry]) {
        ds->parent[rx] = ry;
    } else if (ds->rank[rx] > ds->rank[ry]) {
        ds->parent[ry] = rx;
    } else {
        ds->parent[ry] = rx;
        ds->rank[rx]++;
    }
    return true;
}

/* ---- Kruskal's algorithm ---- */

static int compare_edges(const void *a, const void *b) {
    const Edge *ea = a;
    const Edge *eb = b;
    return (ea->weight > eb->weight) - (ea->weight < eb->weight);
}

static void kruskal_mst(Edge *edges, int edge_count, int vertex_count) {
    /* Step 1: sort all edges by weight, ascending */
    qsort(edges, (size_t)edge_count, sizeof *edges, compare_edges);

    DisjointSet ds;
    if (!ds_init(&ds, vertex_count)) {
        fprintf(stderr, "Out of memory\n");
        return;
    }

    int total_weight = 0;
    int edges_used = 0;

    puts("Edges in the minimum spanning tree:");

    /* Step 2: take edges in order, skipping any that would form a cycle */
    for (int i = 0; i < edge_count && edges_used < vertex_count - 1; i++) {
        if (ds_union(&ds, edges[i].src, edges[i].dest)) {
            printf("  %c -- %c  (weight %d)\n",
                   'A' + edges[i].src, 'A' + edges[i].dest, edges[i].weight);
            total_weight += edges[i].weight;
            edges_used++;
        }
    }

    if (edges_used != vertex_count - 1)
        puts("Warning: the graph is not connected; no spanning tree exists.");
    printf("Total weight of MST: %d\n", total_weight);

    ds_free(&ds);
}

int main(void) {
    /* Vertices A..G are numbered 0..6 */
    Edge edges[] = {
        {0, 1, 7},  /* A-B */
        {0, 3, 5},  /* A-D */
        {1, 2, 8},  /* B-C */
        {1, 3, 9},  /* B-D */
        {1, 4, 7},  /* B-E */
        {2, 4, 5},  /* C-E */
        {3, 4, 15}, /* D-E */
        {3, 5, 6},  /* D-F */
        {4, 5, 8},  /* E-F */
        {4, 6, 9},  /* E-G */
        {5, 6, 11}, /* F-G */
    };
    int edge_count = (int)(sizeof edges / sizeof edges[0]);
    int vertex_count = 7;

    kruskal_mst(edges, edge_count, vertex_count);
    return 0;
}

Output:

Edges in the minimum spanning tree:
  A -- D  (weight 5)
  C -- E  (weight 5)
  D -- F  (weight 6)
  A -- B  (weight 7)
  B -- E  (weight 7)
  E -- G  (weight 9)
Total weight of MST: 39

Exactly the trace from the worked example. To use your own graph, replace the edges array and vertex_count — or read them from a file or stdin with scanf("%d %d %d", &src, &dest, &weight) in a loop.

Kruskal’s Algorithm in C++

The C++ version wraps union-find in a small class and uses std::sort with a lambda comparator. It compiles cleanly with g++ -std=c++17 -Wall -Wextra.

// Kruskal's Algorithm in modern C++ (C++17)
// Compile: g++ -std=c++17 -Wall -Wextra -O2 kruskal.cpp -o kruskal
#include <algorithm>
#include <iostream>
#include <numeric>
#include <vector>

struct Edge {
    int src;
    int dest;
    int weight;
};

class DisjointSet {
public:
    explicit DisjointSet(int n) : parent_(n), rank_(n, 0) {
        std::iota(parent_.begin(), parent_.end(), 0);  // each vertex is its own set
    }

    int find(int x) {
        while (parent_[x] != x) {
            parent_[x] = parent_[parent_[x]];  // path compression
            x = parent_[x];
        }
        return x;
    }

    // Returns false if x and y were already connected
    // (the edge would form a cycle).
    bool unite(int x, int y) {
        int rx = find(x);
        int ry = find(y);
        if (rx == ry) return false;

        if (rank_[rx] < rank_[ry]) std::swap(rx, ry);  // union by rank
        parent_[ry] = rx;
        if (rank_[rx] == rank_[ry]) ++rank_[rx];
        return true;
    }

private:
    std::vector<int> parent_;
    std::vector<int> rank_;
};

std::vector<Edge> kruskalMST(int vertexCount, std::vector<Edge> edges,
                             int& totalWeight) {
    // Step 1: sort edges by weight, ascending
    std::sort(edges.begin(), edges.end(),
              [](const Edge& a, const Edge& b) { return a.weight < b.weight; });

    DisjointSet ds(vertexCount);
    std::vector<Edge> mst;
    mst.reserve(vertexCount - 1);
    totalWeight = 0;

    // Step 2: take edges in order, skipping any that would form a cycle
    for (const Edge& e : edges) {
        if (static_cast<int>(mst.size()) == vertexCount - 1) break;
        if (ds.unite(e.src, e.dest)) {
            mst.push_back(e);
            totalWeight += e.weight;
        }
    }
    return mst;
}

int main() {
    const int vertexCount = 7;  // vertices A..G are numbered 0..6
    std::vector<Edge> edges = {
        {0, 1, 7},  {0, 3, 5},  {1, 2, 8}, {1, 3, 9}, {1, 4, 7},  {2, 4, 5},
        {3, 4, 15}, {3, 5, 6},  {4, 5, 8}, {4, 6, 9}, {5, 6, 11},
    };

    int totalWeight = 0;
    std::vector<Edge> mst = kruskalMST(vertexCount, edges, totalWeight);

    if (static_cast<int>(mst.size()) != vertexCount - 1) {
        std::cout << "The graph is not connected; no spanning tree exists.\n";
        return 1;
    }

    std::cout << "Edges in the minimum spanning tree:\n";
    for (const Edge& e : mst) {
        std::cout << "  " << char('A' + e.src) << " -- " << char('A' + e.dest)
                  << "  (weight " << e.weight << ")\n";
    }
    std::cout << "Total weight of MST: " << totalWeight << '\n';
    return 0;
}

The output is identical to the C version. Note two idioms worth stealing for your own code: unite() returns bool, so cycle detection and merging are one call, and std::swap(rx, ry) collapses the union-by-rank branches into two lines.

Kruskal’s Algorithm in Python

The same algorithm and the same graph, in Python — useful for comparing how much of the C/C++ code is bookkeeping:

"""Kruskal's Algorithm in Python using union-find (disjoint set)."""

class DisjointSet:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n

    def find(self, x):
        while self.parent[x] != x:
            self.parent[x] = self.parent[self.parent[x]]  # path compression
            x = self.parent[x]
        return x

    def union(self, x, y):
        rx, ry = self.find(x), self.find(y)
        if rx == ry:
            return False  # already connected: edge would form a cycle
        if self.rank[rx] < self.rank[ry]:
            rx, ry = ry, rx  # union by rank
        self.parent[ry] = rx
        if self.rank[rx] == self.rank[ry]:
            self.rank[rx] += 1
        return True


def kruskal(vertex_count, edges):
    """Return (mst_edges, total_weight) for an undirected weighted graph."""
    ds = DisjointSet(vertex_count)
    mst, total_weight = [], 0

    for u, v, weight in sorted(edges, key=lambda e: e[2]):
        if len(mst) == vertex_count - 1:
            break
        if ds.union(u, v):
            mst.append((u, v, weight))
            total_weight += weight

    return mst, total_weight


if __name__ == "__main__":
    # Vertices A..G are numbered 0..6 — the same graph as the C and C++ examples.
    edges = [
        (0, 1, 7), (0, 3, 5), (1, 2, 8), (1, 3, 9), (1, 4, 7), (2, 4, 5),
        (3, 4, 15), (3, 5, 6), (4, 5, 8), (4, 6, 9), (5, 6, 11),
    ]
    mst, total = kruskal(7, edges)

    print("Edges in the minimum spanning tree:")
    for u, v, w in mst:
        print(f"  {chr(65 + u)} -- {chr(65 + v)}  (weight {w})")
    print(f"Total weight of MST: {total}")

Time and Space Complexity

The practical takeaway: sorting is the bottleneck. If your edges arrive pre-sorted (or you can use a linear-time sort on integer weights), Kruskal’s algorithm runs in near-linear time.

Kruskal vs Prim: Which One Should You Use?

Both are greedy MST algorithms and both produce a correct MST. They differ in how they grow the tree:

Rule of thumb: given an edge list and a sparse graph, use Kruskal. Given an adjacency list and a dense graph, use Prim.

Real-World Applications

• Network design — laying out fiber, electrical grids, or pipelines that connect every site at minimum total cost is the textbook MST problem.
• Clustering — single-linkage hierarchical clustering is Kruskal’s algorithm stopped early: leave out the k − 1 heaviest MST edges and you get k clusters.
• Image segmentation — graph-based segmentation treats pixels as vertices and color differences as weights, then builds MST-like structures to group regions.
• Approximation algorithms — the classic 2-approximation for the metric Traveling Salesman Problem starts from an MST.
• Maze generation — running Kruskal’s on a grid with random edge weights produces uniform random mazes.

Key Takeaways

• Kruskal’s algorithm builds an MST by sorting edges and greedily accepting any edge that doesn’t create a cycle.
• Union-find with path compression and union by rank is what makes cycle detection effectively O(1) — implement it, don’t fake it with searches.
• Total complexity is O(E log E), dominated by the sort; space is O(V + E).
• Prefer Kruskal for sparse graphs and edge-list input; prefer Prim for dense graphs with adjacency lists.
• The C, C++, and Python programs above are complete and tested — all three print the same MST (total weight 39) for the same example graph.

Frequently Asked Questions

Conclusion

Kruskal’s algorithm endures because the elegant idea and the practical implementation are the same thing: sort once, then let a well-built union-find make every cycle check trivial. The pattern underneath it — a greedy choice justified by a structural property, made fast by the right data structure — transfers to far more problems than spanning trees.

The natural next steps are Prim’s algorithm for the dense-graph case and Borůvka’s algorithm for the parallel one; both build on the MST foundations covered across our algorithms section, and both make more sense once you’ve traced Kruskal’s by hand the way this article does.