Minimum spanning trees: Kruskal

What this chapter covers

Last chapter built a minimum spanning tree by growing one tree outward from a seed. Kruskal's algorithm builds the same tree by the opposite philosophy: forget any starting point, sort every edge from cheapest to most expensive, and walk down the list adding each edge unless it would connect two nodes that are already connected. It starts with a forest of V lonely single-node trees and fuses them, cheapest edge first, until they've all merged into one. The single question it asks over and over — "are these two nodes already in the same tree?" — is exactly what the union-find structure from the trees tier answers in near-constant time, which makes Kruskal that structure's headline application. This chapter builds it, watches the forest merge edge by edge, and uses it to reveal something worth seeing: on a graph of a quarter-million edges, the entire union-find bookkeeping takes under two milliseconds — Kruskal's real cost is the sort, and union-find is essentially free.

A bit of history

Joseph Kruskal published the algorithm in 1956, in a short and elegant paper in the Proceedings of the American Mathematical Society, a year before Prim's rediscovery of Prim's. It's one of the earliest algorithms whose correctness rests on what we'd now call a greedy-exchange argument, and Kruskal's paper is admirably direct: sort the edges, add each that doesn't make a cycle, and he proves that yields the minimum. What the paper couldn't yet name was the data structure that makes the cycle test fast — union-find with path compression and union by rank wasn't analyzed until the 1970s, by Robert Tarjan, who proved its astonishing near-constant amortized bound. So Kruskal's algorithm is a nice historical layering: a 1956 greedy method whose efficiency waited two decades for the 1970s data structure that powers it. The two ideas together — a simple greedy rule and a fast disjoint-set structure — are why Kruskal is both easy to state and fast to run.

The intuition

Picture every node as its own tiny tree — a forest of V separate one-node trees, nothing connected to anything. Sort all the edges by weight, cheapest first. Now go down the list. For each edge, ask: do its two endpoints already belong to the same tree? If they're in different trees, this edge joins two separate pieces of the forest into one larger tree — add it, and it's part of your minimum spanning tree. If they're already in the same tree, then adding this edge would create a cycle (there's already a path between them), so skip it. Keep going until you've added V−1 edges, at which point the whole forest has merged into a single spanning tree.

Why cheapest-first? Because of the cut property from last chapter: the cheapest edge crossing any divide between connected and unconnected pieces is safe to include. By processing edges in sorted order, every edge Kruskal accepts is the cheapest one available that connects two particular components — the cut property guarantees it belongs to some minimum spanning tree. The only machinery Kruskal needs is a way to track which nodes are in which tree and to merge two trees when an edge joins them, fast, because it does that test once per edge. That's the union-find (disjoint-set) structure: find(x) returns which tree a node belongs to, union(a, b) merges two trees, and with path compression and union by rank both run in effectively constant time. Kruskal is where union-find stops being an abstract exercise and becomes the thing that makes a real algorithm fast.

Complexity: how it scales

Kruskal is $O(E \log E)$, and that cost is almost entirely the initial sort of the edges. The pass that follows — one union-find operation per edge — is effectively $O(E \cdot \alpha(V))$, where $\alpha$ is the inverse Ackermann function, which is at most 4 for any input that will ever exist. So the union-find work is practically linear, and the sort dominates. The face-off makes this concrete by timing three things as the graph gets denser: full Kruskal, Prim, and — the revealing one — just Kruskal's union-find pass on edges that are already sorted:

Full Kruskal and Prim run neck and neck across all densities — on a 1500-node graph they were within a few percent, Prim marginally ahead — so in practice the choice between them is rarely about speed. But look at the bottom line: on the densest graph, roughly a quarter-million edges, full Kruskal took about 133 ms while the union-find pass alone, on pre-sorted edges, took under 2 ms. The sort is 98% of Kruskal's work; the cycle-detection-and-merging is nearly free. That's the payoff of union-find's near-constant operations, and it tells you exactly when Kruskal wins: whenever the edges are already sorted, or can be sorted cheaply (bucket or radix sort on integer weights), Kruskal drops to nearly linear and beats everything.

What it's good at, what it isn't

Kruskal is the right tool for minimum spanning trees when you're working from an edge list (rather than adjacency), when the graph is sparse, when edges are already or cheaply sortable, or when you want the more parallel-friendly of the two classic algorithms. Its logic is transparent — sort, then add-if-no-cycle — which makes it a favorite for teaching and for correctness-critical code. It's also the natural expression of MST-based clustering: run Kruskal but stop early, after V−k merges instead of V−1, and you've partitioned the graph into exactly k clusters, each a connected piece joined by cheap edges (this is single-linkage clustering, and stopping Kruskal early is the cleanest way to see it).

Where Kruskal is less ideal is dense graphs held as adjacency structures, where sorting all $\Theta(V^2)$ edges is wasteful and Prim's frontier — which only ever looks at edges touching the current tree — does less work. It also, like Prim, produces a structure people misuse: a minimum spanning tree is not a shortest-path tree, and the tree-path between two nodes can be far longer than their real shortest path. And Kruskal needs all the edges available up front to sort them, so it isn't suited to streaming graphs where edges arrive over time and a decision is needed immediately.

The data, or the inputs

The face-off runs on 1500-node random connected graphs of increasing density and times three strategies: full Kruskal (sort + union-find), Prim (priority queue), and Kruskal's union-find pass alone on pre-sorted edges — the last isolating how cheap the disjoint-set work really is. Correctness is cross-checked against Prim (last chapter's independent algorithm): on hundreds of random graphs Kruskal's total weight must equal Prim's, and the result must be a spanning tree of V−1 edges reaching every node. The animation runs Kruskal on the same small weighted graph Prim solved last chapter (so the total, 15, matches), coloring each node by which tree it currently belongs to — so you can literally watch separate colors merge into one as edges are accepted.

Build it, one function at a time

The union-find engine — the near-constant-time cycle test at Kruskal's heart:

class DSU:
    """Disjoint-set union (union-find) with path compression and union by rank — the engine
    that makes Kruskal fast. `find` returns a canonical representative of a node's set;
    `union` merges two sets. Both run in near-constant amortized time (inverse Ackermann),
    so the union-find work across all of Kruskal is effectively linear."""

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

    def find(self, x):
        root = x
        while self.parent[root] != root:
            root = self.parent[root]
        while self.parent[x] != root:            # path compression: point everyone at the root
            self.parent[x], x = root, self.parent[x]
        return root

    def union(self, a, b):
        """Merge the sets of a and b. Returns False if they were already the same set (so the
        edge would make a cycle), True if a real merge happened."""
        ra, rb = self.find(a), self.find(b)
        if ra == rb:
            return False                         # already connected → adding this edge cycles
        if self.rank[ra] < self.rank[rb]:        # hang the shorter tree under the taller
            ra, rb = rb, ra
        self.parent[rb] = ra
        if self.rank[ra] == self.rank[rb]:
            self.rank[ra] += 1
        return True

And Kruskal itself — sort, then add every edge that joins two different trees:

def kruskal(edges, n):
    """Minimum spanning tree by Kruskal's method. `edges` is a list of (u, v, w). Sort all
    edges ascending by weight; for each, add it iff its endpoints are in different components
    (union succeeds). Stop once V−1 edges are chosen. O(E log E) — dominated by the sort;
    the union-find work is effectively linear. Returns (mst_edges, total_weight)."""
    dsu = DSU(n)
    mst_edges = []
    total = 0
    for w, u, v in sorted((w, u, v) for u, v, w in edges):
        if dsu.union(u, v):                      # different trees → safe to add, merges them
            mst_edges.append((u, v, w))
            total += w
            if len(mst_edges) == n - 1:          # a spanning tree is complete at V−1 edges
                break
    return mst_edges, total

Watch it work

Here's Kruskal on the same graph Prim built last chapter. Each node is colored by which tree it belongs to — at the start all seven are different colors, seven separate one-node trees. Edges are considered cheapest-first: a solid orange flash means "accepted" (its endpoints were different colors, so it merges two trees and they adopt one color), and a dashed red flash means "rejected" (its endpoints are already the same color — same tree — so it would make a cycle). Watch the colors coalesce: weight-1 edge first, then weight-2, and each acceptance fuses two colors into one, until all seven nodes share a single color and the forest has become one tree of total weight 15 — the identical minimum Prim found, reached by merging instead of growing:

The complete code

The from-scratch tab is Kruskal with its union-find engine; the library tab is Prim — last chapter's algorithm, used here as the independent reference Kruskal's total is checked against — with the networkx/scipy calls you'd use in production noted. Flip between them.

"""Kruskal's algorithm — the same minimum spanning tree Prim builds, by the opposite
strategy. Where Prim grows one tree outward from a seed, Kruskal ignores any starting point
and thinks globally about edges: sort every edge cheapest-first, then walk down that list
adding each edge UNLESS it would connect two nodes that are already connected (which would
form a cycle). Add V−1 safe edges and you have the minimum spanning tree.

Kruskal starts with a FOREST of V separate one-node trees and merges them. Each accepted
edge fuses two trees into one; each rejected edge would have joined a tree to itself. The
one operation it needs — over and over — is "are these two nodes already in the same tree?"
and, if not, "merge their trees." That is precisely the union-find (disjoint-set) structure
from the trees tier, and Kruskal is its headline application: this chapter is where union-find
finally earns its near-constant-time find and union.
"""


# region: dsu
class DSU:
    """Disjoint-set union (union-find) with path compression and union by rank — the engine
    that makes Kruskal fast. `find` returns a canonical representative of a node's set;
    `union` merges two sets. Both run in near-constant amortized time (inverse Ackermann),
    so the union-find work across all of Kruskal is effectively linear."""

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

    def find(self, x):
        root = x
        while self.parent[root] != root:
            root = self.parent[root]
        while self.parent[x] != root:            # path compression: point everyone at the root
            self.parent[x], x = root, self.parent[x]
        return root

    def union(self, a, b):
        """Merge the sets of a and b. Returns False if they were already the same set (so the
        edge would make a cycle), True if a real merge happened."""
        ra, rb = self.find(a), self.find(b)
        if ra == rb:
            return False                         # already connected → adding this edge cycles
        if self.rank[ra] < self.rank[rb]:        # hang the shorter tree under the taller
            ra, rb = rb, ra
        self.parent[rb] = ra
        if self.rank[ra] == self.rank[rb]:
            self.rank[ra] += 1
        return True
# endregion


# region: kruskal
def kruskal(edges, n):
    """Minimum spanning tree by Kruskal's method. `edges` is a list of (u, v, w). Sort all
    edges ascending by weight; for each, add it iff its endpoints are in different components
    (union succeeds). Stop once V−1 edges are chosen. O(E log E) — dominated by the sort;
    the union-find work is effectively linear. Returns (mst_edges, total_weight)."""
    dsu = DSU(n)
    mst_edges = []
    total = 0
    for w, u, v in sorted((w, u, v) for u, v, w in edges):
        if dsu.union(u, v):                      # different trees → safe to add, merges them
            mst_edges.append((u, v, w))
            total += w
            if len(mst_edges) == n - 1:          # a spanning tree is complete at V−1 edges
                break
    return mst_edges, total
# endregion

"""The library counterpart, the independent reference, and the rival. In production a
minimum spanning tree comes from networkx or scipy — networkx's default is actually Kruskal:

    import networkx as nx
    T = nx.minimum_spanning_tree(G, weight="weight", algorithm="kruskal")

The reference/rival that makes Kruskal legible is PRIM (last chapter) — the other MST
algorithm, which grows one tree from a seed using a priority queue instead of sorting edges
and merging a forest. They pick possibly-different trees but always the same total weight,
so Prim is the ground truth for Kruskal's total, and the trace generator times both to show
which wins at which density.
"""
import heapq


# region: prim
def prim(adj, n, start=0):
    """Prim's MST from the last chapter: grow one tree, always adding the cheapest edge that
    crosses from the tree to the outside, via a min-heap keyed on edge weight. O(E log V).
    Independent of Kruskal's sort-and-merge approach, so it's the reference for the total."""
    in_tree = [False] * n
    in_tree[start] = True
    total, count = 0, 0
    pq = [(w, v) for v, w in adj[start]]
    heapq.heapify(pq)
    while pq and count < n - 1:
        w, v = heapq.heappop(pq)
        if in_tree[v]:
            continue
        in_tree[v] = True
        total += w
        count += 1
        for c, wc in adj[v]:
            if not in_tree[c]:
                heapq.heappush(pq, (wc, c))
    return total
# endregion

Scratch vs library

Kruskal is a satisfying reunion of two threads of this book: the greedy cut-property logic shared with Prim, and the union-find structure from the trees tier, meeting in one algorithm where each makes the other work. That's the real lesson here — not "Kruskal versus Prim" (they're near-identical in speed and reach the same tree) but how a classic algorithm is a composition of a strategy and a data structure, and how the data structure's quality decides the algorithm's cost. The 2-millisecond union-find pass on a quarter-million edges is the whole justification for having spent a chapter on disjoint sets: without path compression and union by rank, that pass would be the bottleneck; with them, it vanishes and the sort is all that's left. In production you'd call networkx.minimum_spanning_tree (which defaults to Kruskal) or scipy's compiled version; building it yourself is what turns "union-find is near-constant" from a memorized bound into a number you've measured, and what makes the choice between Kruskal and Prim a reasoned one — edge list and sparse or pre-sorted, reach for Kruskal; adjacency and dense, reach for Prim.

Where you'll actually meet it

Kruskal shares Prim's application space — least-cost network design for power grids, telecom, pipes, cable, and circuit layout — and adds a few of its own. It's the standard method behind single-linkage hierarchical clustering: build the MST, and its edges, cut in decreasing order, are exactly the cluster-merge history of the data. Image-segmentation algorithms (Felzenszwalb-Huttenlocher) are Kruskal-style region merging. It seeds approximation algorithms for the traveling salesman problem. It generates perfect mazes (a random-weight MST of a grid graph). Its parallel cousin Borůvka's algorithm, which repeatedly merges every component with its cheapest outgoing edge at once, powers distributed MST computation on massive graphs. And because it's so transparent, Kruskal is the MST algorithm most often reached for when correctness and clarity matter more than squeezing out the last constant factor.

Takeaways

Kruskal's algorithm builds a minimum spanning tree by sorting all edges cheapest-first and adding each one that joins two different trees — detecting cycles with union-find — in $O(E \log E)$, dominated entirely by the sort. It reaches the identical tree Prim does, from the opposite direction: merging a forest rather than growing one tree, its correctness resting on the same cut property. Its union-find engine is what makes it fast, and measuring that engine — a quarter-million merges in under two milliseconds — is the clearest possible payoff of the trees tier's disjoint-set chapter. Kruskal and Prim are the two faces of minimum spanning trees, and which you pick is about edge representation and setting, never about which finds a cheaper tree.

That closes the constructive graph algorithms. The final chapter of the tier returns to analysis of a directed graph's structure: its strongly connected components — the maximal groups of nodes that can all reach each other. Finding them is a beautiful two-pass depth-first search (Kosaraju's algorithm) or a single clever one (Tarjan's), and it completes the graph tier by tying back to the depth-first search where it began.