Kruskal's MST Deep Dive, in depth: the matroid reason greedy works, where the time goes, float keys and deterministic ties, incremental updates, Euclidean MST and verification

Why greedy works: the matroid view

Kruskal is an instance of a more general theorem. A matroid is a ground set with a family of "independent" subsets that is closed under taking subsets and satisfies an exchange property: if one independent set is larger than another, some element of the larger one can be added to the smaller one and keep it independent. The forests of a graph form a matroid, the graphic matroid. Its ground set is the edges, and an edge set is independent when it has no cycle. The exchange property holds because a forest with more edges has fewer components, so one of its edges must join two components of the smaller forest.

The Rado-Edmonds theorem says the greedy algorithm (scan the elements by weight and keep each one that preserves independence) finds an optimal basis for every weight function exactly when the structure is a matroid. Kruskal is that greedy algorithm on the graphic matroid. The same theorem explains other greedy successes. Picking a maximum-weight set of linearly independent vectors works the same way, using a linear matroid.

It also explains failures. Add a constraint that breaks the exchange property and greedy stops being safe. A spanning tree in which every vertex has degree at most 2 is a Hamiltonian path, so the degree-constrained MST is NP-hard. The Steiner tree problem, which must connect only some vertices and may use others, is NP-hard as well. When a colleague proposes "Kruskal, but skip edges that violate X", ask whether X keeps the matroid structure. If it does not, the result is a heuristic with no guarantee.

Where the time actually goes

The textbook bound is O(m log m) for the sort plus O(m α(n)) for the union-find operations, where α is the inverse Ackermann function and is at most 4 for any input you will meet. In practice the sort dominates. The union-find loop is a few array reads per edge and often stops early, because once n - 1 edges are accepted the tree is complete and the remaining edges can be skipped. Early exit saves union-find work, not the sort, which has already been paid for in full.

So performance work on Kruskal is mostly performance work on the sort. Sort compact records rather than objects. Use an integer key where you can, because integer sorts, including radix sorts, are much faster than comparison sorts on boxed floats. If the graph is so large that sorting everything is wasteful, filter-Kruskal partitions edges around a pivot and discards heavy edges inside already-connected components before sorting them. The animated article covers that variant.

Sort keys: floats, NaN and ties

Two details decide whether an implementation is correct and reproducible. The first is float weights. NaN compares false with everything, so a NaN weight leaves the sort order undefined and can silently produce a non-minimal tree. Reject NaN at input. If you want an integer key for a fast sort, map IEEE 754 doubles to unsigned integers that sort in the same order: set the sign bit for non-negative values and flip all bits for negative ones. Add 0.0 first so that -0.0 and +0.0 map to the same key.

import struct

def float_key(x: float) -> int:
    """Map a double to a uint64 with the same ordering. Rejects NaN."""
    if x != x:
        raise ValueError("NaN edge weight")
    x = x + 0.0                                   # turns -0.0 into +0.0
    (bits,) = struct.unpack(">Q", struct.pack(">d", x))
    return bits ^ 0xFFFF_FFFF_FFFF_FFFF if bits >> 63 else bits | (1 << 63)

The second is ties. With equal weights there can be several minimum spanning trees, all with the same total weight. That is fine mathematically, but a pipeline that rebuilds a tree nightly and diffs it, or a clustering job whose output feeds a cache, needs the same tree each time. Python's sort is stable, but the input order often comes from a hash map or a parallel loader and varies between runs. Make the key total: sort by (weight, min endpoint, max endpoint). Equal weights then break by vertex IDs, and the tree is unique for a given input.

A production implementation

Here is a complete implementation built from those rules. The union-find uses flat lists, union by size and iterative path halving, so deep trees cannot hit Python's recursion limit. The function returns a spanning forest if the graph is disconnected, and the caller can check the edge count. The union-find structure itself is explained in union-find, in depth.

def kruskal(n: int, edges: list[tuple[float, int, int]]):
    """edges: (weight, u, v). Returns (total, tree_edges). A forest if disconnected."""
    parent = list(range(n))
    size = [1] * n

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

    keyed = []
    for w, u, v in edges:
        if w != w:
            raise ValueError("NaN edge weight")
        if u != v:                               # self-loops never join components
            keyed.append((w, min(u, v), max(u, v)))
    keyed.sort()                                 # total order: weight, then vertex ids

    total, tree = 0.0, []
    for w, u, v in keyed:
        ru, rv = find(u), find(v)
        if ru == rv:
            continue                             # would close a cycle
        if size[ru] < size[rv]:
            ru, rv = rv, ru
        parent[rv] = ru
        size[ru] += size[rv]
        total += w
        tree.append((u, v, w))
        if len(tree) == n - 1:
            break                                # early exit: the tree is complete
    return total, tree

Note what the function does not do. It does not fail on a disconnected graph, because a spanning forest is often what the caller wants, for example in clustering. Callers who need a tree must check len(tree) == n - 1.

Worked example

Take six vertices A to F (numbered 0 to 5) with the edges A-B 4, A-C 4, B-C 2, B-D 5, C-D 8, C-E 10, D-E 2, D-F 6 and E-F 3. The sorted order with the tie-break is B-C 2, D-E 2, E-F 3, A-B 4, A-C 4, B-D 5, D-F 6, C-D 8, C-E 10. Kruskal accepts B-C, D-E, E-F and A-B. It rejects A-C, because A, B and C are already connected, then accepts B-D. That makes five edges for six vertices, so it stops without looking at the last three. The total is 2 + 2 + 3 + 4 + 5 = 16.

The tie between A-B and A-C matters. Had A-C come first, the tree would use A-C instead of A-B: a different tree with the same weight of 16. The tie-break in the key is what makes the output repeatable.

Inserting an edge without a rebuild

Graphs change. When a new edge (u, v, w) arrives, there is no need to rerun Kruskal. Adding the edge to the current tree creates exactly one cycle: the tree path from u to v plus the new edge. By the cycle property, the heaviest edge on that cycle cannot be in a minimum spanning tree. If that edge is the new one, discard it. Otherwise swap it out.

def insert_edge(adj: dict, u: int, v: int, w: float) -> float:
    """adj: tree adjacency {x: {y: weight}}. Returns the change in total weight."""
    if u == v:
        return 0.0                               # a self-loop never joins the tree
    path = tree_path(adj, u, v)                  # list of (a, b, weight); O(n) by DFS
    if not path:                                 # u and v were in different trees
        adj[u][v] = adj[v][u] = w
        return w
    a, b, heavy = max(path, key=lambda e: e[2])
    if heavy <= w:
        return 0.0                               # new edge is the cycle maximum
    del adj[a][b], adj[b][a]
    adj[u][v] = adj[v][u] = w
    return w - heavy

In the example, inserting A-F with weight 3 gives the tree path A-B (4), B-D (5), D-E (2), E-F (3). The maximum is B-D at 5, which is greater than 3, so B-D leaves and A-F joins. The new total is 16 - 5 + 3 = 14, which matches a fresh Kruskal run on the new graph. A naive path walk costs O(n) per insertion. Link-cut trees bring this to O(log n) amortised. Deletions are harder, because removing a tree edge requires finding the lightest replacement across the cut, and fully dynamic MST structures are complex. In practice, batch the deletions and rebuild, which is cheap when the sort dominates and the data fits in memory.

Euclidean MST at scale

A Euclidean MST of n points is defined on the complete graph, which has n(n - 1)/2 edges. For a million points that is about 5 × 10¹¹ edges, far too many to sort. In the plane there is a better way. The Euclidean MST is a subgraph of the Delaunay triangulation, which has at most 3n - 6 edges and can be built in O(n log n). So triangulate, then run Kruskal on the Delaunay edges.

import numpy as np
from scipy.spatial import Delaunay

def emst_2d(pts: np.ndarray):
    pts = np.unique(pts, axis=0)                 # duplicates break the triangulation
    tri = Delaunay(pts)                          # raises on all-collinear input
    pairs = set()
    for a, b, c in tri.simplices:
        for u, v in ((a, b), (b, c), (a, c)):
            pairs.add((min(u, v), max(u, v)))
    edges = [(float(np.linalg.norm(pts[u] - pts[v])), int(u), int(v)) for u, v in pairs]
    total, tree = kruskal(len(pts), edges)
    assert len(tree) == len(pts) - 1
    return pts, total, tree

In high dimensions, such as embedding vectors, Delaunay is impractical. The standard approach is to build an approximate k-nearest-neighbour graph and run Kruskal on it. The result is approximate, and a kNN graph can be disconnected, so Kruskal returns a forest. Join the components afterwards with their closest cross-component pairs, and record that the result is not exact. Density-based clustering builds on exactly this kind of tree; see DBSCAN, in depth for the density side.

Verifying a tree you were given

To check that a spanning tree T is minimal, use the cycle property as a certificate. T is an MST if and only if, for every non-tree edge (u, v), its weight is at least the maximum weight on the tree path from u to v. With path-maximum queries from binary lifting, the check takes O(m log n). Linear-time verification algorithms exist but are rarely worth the complexity. The same path-maximum machinery solves the second-best MST problem, described in second-best MST. In tests, also compare the total against brute force on small random graphs with many tied weights, because ties are where bugs hide.

Failure modes

• NaN weights silently corrupt the order. Reject them at input.
• Non-deterministic ties produce different but equally minimal trees from run to run, which breaks diffing and caching.
• Disconnected input returns a forest. Code that assumes n - 1 edges reads past the end.
• Zero as "no edge". Dense-matrix graph APIs often treat 0 as a missing edge, so zero-weight edges vanish. Check your library's convention.
• Recursive find overflows the stack on adversarial union orders without union by size.
• Greedy on a non-matroid. Adding a degree or budget constraint and keeping the greedy loop gives a heuristic, not an optimum.

What to do next

1. Replace object-based edge lists with compact (weight, u, v) tuples or arrays, and measure how much of the time is the sort.
2. Reject NaN, normalise -0.0, and use the total (weight, min, max) key.
3. Use union by size with iterative path halving, and exit after n - 1 edges.
4. For streams of insertions, use the cycle-swap update. For deletions, batch and rebuild.
5. For points in the plane, run Kruskal on Delaunay edges. For embeddings, use a kNN graph and document the approximation.
6. Add a cycle-property verifier and a brute-force test with tied weights to the test suite.