Kruskal's Minimum Spanning Tree, in depth: sort-and-filter greedy, the cycle property, union-find, clustering and the reconstruction tree

The problem

Take a connected undirected graph with V vertices and E edges, each with a real weight. A spanning tree is a subset of exactly V - 1 edges that connects all vertices and contains no cycle. Its weight is the sum of its edge weights, and an MST is a spanning tree of minimum weight. Negative weights are allowed and change nothing, because every spanning tree has the same number of edges; adding a constant to all weights shifts every tree's total equally.

Typical uses include laying cable between sites at minimum cost, network backbones, image segmentation and approximation algorithms such as the 2-approximation for metric travelling salesman.

Why the greedy rule is optimal

Kruskal relies on two facts. The cut property says that for any split of the vertices into two sides, the lightest edge crossing the split belongs to some MST. The cycle property says that for any cycle, an edge that is strictly heavier than every other edge on that cycle belongs to no MST, because swapping it for a lighter cycle edge reconnects the tree more cheaply.

Now look at the moment Kruskal examines edge (u, v) with weight w. Two cases arise.

1. u and v are already connected by the edges chosen so far. Every one of those edges was examined earlier, so each weighs at most w. Adding (u, v) would close a cycle on which it is a heaviest edge. By the cycle property (in its tie-tolerant form, some MST avoids a maximum edge on any cycle), skipping it is safe.
2. u and v are in different components. Let S be u's component. No edge leaving S has been accepted yet, and every edge leaving S that is lighter than w would already have been examined and accepted, which contradicts S still being separate. So (u, v) is a lightest edge crossing the cut between S and everything else, and the cut property says it is safe to take.

An induction over the sorted order turns this into a proof: after every step, the chosen edges are a subset of some MST, and after V - 1 acceptances they are one.

Worked example, traced by hand

The figure uses six vertices and nine edges, labelled by weight. Sorting gives the order 1 to 9, and a union-find structure tracks which vertices are already joined.

The tree has weight 20. Edge D-F with weight 9 is never examined, because five edges already span six vertices. Check the skip of A-B: it would close the cycle A-C-B with edges of weight 1 and 3, both lighter than 4, so A-B is the maximum on that cycle exactly as the proof says.

A complete implementation

The implementation is a sort followed by a loop over a disjoint-set forest. Union by size keeps trees shallow and path halving flattens them during finds, together giving amortised near-constant time per operation. The find is iterative, which matters in Python, where a recursive find on a long chain hits the recursion limit.

def kruskal(n, edges):
    """n vertices labelled 0..n-1; edges is a list of (weight, u, v).
    Returns (total_weight, tree_edges). If the graph is disconnected the
    result is a minimum spanning forest with fewer than n - 1 edges."""
    parent = list(range(n))
    size = [1] * n

    def find(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]   # path halving
            x = parent[x]
        return x

    def union(a, b):
        ra, rb = find(a), find(b)
        if ra == rb:
            return False                    # would close a cycle
        if size[ra] < size[rb]:
            ra, rb = rb, ra
        parent[rb] = ra                     # attach smaller under larger
        size[ra] += size[rb]
        return True

    total, tree = 0, []
    for w, u, v in sorted(edges):           # sort by weight, then u, v
        if union(u, v):
            total += w
            tree.append((u, v, w))
            if len(tree) == n - 1:          # early exit: tree complete
                break
    return total, tree

Sorting tuples as (weight, u, v) is deliberate: the tie-break on endpoints makes the output deterministic, which keeps tests and diffs stable. The cost is dominated by the sort, O(E log E), which equals O(E log V) because E is at most V squared. The union-find work is O(E alpha(V)), where alpha is the inverse Ackermann function and is at most 4 for any input that fits in the universe. With small integer weights, a radix sort removes the log factor.

Forests, ties and other variants

Several common requirements are one-line changes to the same loop.

• Disconnected input. The loop naturally produces a minimum spanning forest: one MST per component. Detect it by checking whether the tree has fewer than V - 1 edges, and report the component count (V minus accepted edges) instead of silently returning a forest where a tree was promised.
• Maximum spanning tree. Sort in descending order, or negate the weights. Every proof step carries over with inequalities reversed.
• Minimum bottleneck spanning tree. Every MST also minimises the largest edge weight it uses, so Kruskal answers the bottleneck question too. The bottleneck is simply the weight of the last accepted edge.
• Ties and uniqueness. With distinct weights the MST is unique. With ties, different tie orders can give different trees of equal weight. To test uniqueness, process each group of equal-weight edges in two passes: first count the edges in the group whose endpoints are still in different sets, then union them and count how many were accepted. If the first count exceeds the second for any group, an alternative MST exists.

Kruskal as a clustering algorithm

Stopping Kruskal early is a clustering algorithm. Run the loop until exactly k components remain and those components are the single-linkage clusters of the data: two points end up together whenever a chain of short hops connects them. The result has a clean guarantee. The spacing, the smallest distance between points in different clusters, equals the weight of the next edge Kruskal would have accepted, and no other partition into k clusters has a larger spacing.

Equivalently, build the full MST and delete its k - 1 heaviest edges. The MST version lets you pick k at a visible jump in tree edge weights. Beware chaining: one bridge of close points can merge two natural clusters. On points in the plane, build a sparse candidate graph (for example a Delaunay triangulation, which contains the Euclidean MST) instead of all n squared pairs.

Edge lists that do not fit: external sort and filter-Kruskal

Kruskal reads edges in sorted order, so it adapts naturally to edge lists larger than memory: sort externally (on disk, or with a distributed sort), then stream edges through a union-find that holds only O(V) state. The early exit means the heaviest tail of the file is never read.

When E is much larger than V, most of the sorting work is wasted on heavy edges that will be rejected. Filter-Kruskal (Osipov, Sanders and Singler, 2009) fixes this with quicksort-style recursion: pick a pivot weight, recurse on the light half, then filter the heavy half by discarding every edge whose endpoints are already connected, and only then recurse on what is left. On dense graphs the filtering removes most heavy edges before anyone sorts them.

For distributed graphs, Boruvka's algorithm, which merges every component with its cheapest outgoing edge in parallel rounds, is usually the better base. A common hybrid runs a few Boruvka rounds to shrink the graph, then finishes with Kruskal on one machine.

The Kruskal reconstruction tree and bottleneck queries

A powerful extension is the Kruskal reconstruction tree. Every time the loop accepts an edge of weight w that joins components X and Y, create a new node labelled w whose children are the current roots of X and Y, and make it the root of the merged component. After the loop, the original vertices are the leaves of a binary tree with V - 1 internal nodes, and labels never decrease on the way up.

The payoff is that the heaviest edge on the MST path between any u and v equals the label of their lowest common ancestor. That answers bottleneck queries such as: what is the smallest maximum edge weight over all paths from u to v, or which vertices can u reach using only edges of weight at most x? For the second, climb from u to the highest ancestor whose label is at most x; its subtree is exactly the reachable set. With binary lifting, each query costs O(log V) after O(V log V) preprocessing,.

def reconstruction_tree(n, edges):
    parent = list(range(2 * n - 1))     # union-find over tree nodes
    label = [0] * (2 * n - 1)           # leaves 0..n-1 have label 0
    children = [[] for _ in range(2 * n - 1)]
    nxt = n
    def find(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]
            x = parent[x]
        return x
    for w, u, v in sorted(edges):
        ru, rv = find(u), find(v)
        if ru == rv:
            continue
        parent[ru] = parent[rv] = nxt   # new internal node becomes the root
        label[nxt], children[nxt] = w, [ru, rv]
        nxt += 1
    return label, children, nxt - 1     # root index if the graph is connected

For offline batches of threshold queries, you can also skip the tree: sort the queries by threshold and answer each one while sweeping edges in the same order, which is a classic Kruskal-plus-union-find pattern covered in Union-Find Variants, in depth.

Failure modes

• Sorting by the wrong key. Storing edges as (u, v, w) and calling sort orders them by endpoint, which still produces a spanning tree, just not a minimum one. Always assert the total weight against a reference.
• Union-find without balancing or compression. On adversarial or already-sorted inputs, naive linking builds chains and find degrades to O(V), making the loop quadratic. Use both union by size (or rank) and path compression.
• Directed edges. Feeding a directed graph to Kruskal treats arcs as undirected and returns something that is not a minimum arborescence. Directed problems need a different algorithm such as Chu-Liu/Edmonds.

Testing an implementation

MST code is easy to test well because there are strong oracles. For small random graphs (say up to 8 vertices), enumerate every subset of V - 1 edges, keep the spanning trees and compare the minimum weight with Kruskal's. For larger graphs, compare against an independent Prim implementation; the trees may differ under ties, but the weights must match. Add property checks on every output: exactly V - 1 edges when connected, no cycle (a fresh union-find over the output never rejects an edge), and every non-tree edge at least as heavy as the heaviest tree edge on the path it would close. That last check is a complete certificate of optimality. For the related shortest-path problem, which looks similar but optimises a different objective, see Dijkstra's Algorithm, in depth; an MST does not contain shortest paths in general.

What to do next

1. Implement the kruskal function above in your language, with an iterative find, union by size and the early exit.
2. Hand-trace the six-vertex example and confirm you get weight 20 and the same skips.
3. Write the brute-force oracle for graphs up to 8 vertices and run a few thousand random comparisons.
4. Add the certificate check (each non-tree edge is at least the path maximum) and run it against a Prim implementation on random graphs with many ties.
5. Turn the loop into single-linkage clustering on a small 2-D dataset and choose k from the jumps in tree edge weights.
6. Build the reconstruction tree and answer "reachable using edges of weight at most x" queries; check them against a BFS restricted to light edges.
7. If your edge lists exceed memory, prototype an external sort followed by a streaming union-find, then measure filter-Kruskal on a dense instance.
8. Continue with Prim's algorithm to see when growing one tree beats sorting all edges.