Cairn
algorithms · minimum spanning tree · O(E log E)

↩ back to Minimum Spanning Trees

Kruskal's Algorithm

Given a connected, weighted, undirected graph, a minimum spanning tree (MST) is the cheapest possible set of edges that still connects every node — a tree (no cycles), touching every vertex, with the smallest total edge weight of any tree that does. Kruskal's algorithm builds one with a strategy simple enough to state in a sentence: sort every edge by weight, cheapest first, and walk the list adding each edge unless it would close a cycle with edges already added. That's the whole algorithm. The only real work is answering "would this edge close a cycle?" fast, for every one of the graph's edges — and that's exactly the question Union-Find was built to answer in near-constant time, which is why the two are usually taught as a pair. It's one of three standard ways to build an MST — Prim's algorithm grows a single tree outward from one node instead of sorting the whole edge list up front, and Borůvka's algorithm takes a third approach again, letting every component pick its own cheapest edge out in simultaneous rounds instead of a single global sort or a single growing frontier.

Try it

Seven waypoints on a trail network, with a cost to cut a trail between each pair (elevation gain, roughly). Press Step or Run to walk the sorted edge list, cheapest first: a black-bordered pair of nodes is the edge currently under consideration, an accepted edge turns solid and orange, a rejected edge turns dashed and fades — rejected because Union-Find reports its two endpoints are already in the same set, meaning some earlier, cheaper path already connects them and this edge would only close a loop. The strip below the graph mirrors the same sorted list as chips; the strip below that shows the live partition into connected sets, the same widget the Union-Find page uses for exactly the same idea.

accepted: 0 / 6 edges · total weight: 0
Press Step or Run.

Why it works

The greedy choice — always take the cheapest edge that doesn't close a cycle — is safe because of what's called the cut property: for any way of splitting the graph's nodes into two non-empty groups, the single cheapest edge crossing that split must belong to some minimum spanning tree. (If it didn't, swapping it in for whatever crossing edge the tree used instead could only make that tree cheaper, contradicting that the tree was already minimum.) Kruskal's sorted-order walk keeps satisfying this property one edge at a time without ever having to think about splits explicitly: when the algorithm accepts an edge, it's always the cheapest one connecting the two sets its endpoints currently belong to, since every cheaper edge either already got processed (and either joined those sets earlier or connected two different sets entirely) or would have been rejected for closing a cycle. Repeat that for every accepted edge and the whole tree ends up minimum, not just each piece of it.

The cycle check is where Union-Find does all the work: two nodes are in the same set exactly when some earlier accepted edge already connects them (directly or transitively), so "would this edge close a cycle?" is just connected(a, b), and "accept it" is just union(a, b). No graph traversal needed on every edge, which is what would make an MST algorithm built on repeated DFS/BFS reachability checks needlessly slow.

Reference implementation

Matches the demo above one for one — same sort, same Union-Find (two-pass path compression + union by rank, identical to the version on the Union-Find page), just without the yield points the demo uses to show every intermediate accept and reject:

function kruskalMST(numNodes, edges) {
  // edges: [{ a, b, w }, ...] — undirected, weight w
  const sorted = edges.slice().sort((x, y) => x.w - y.w);
  const parent = Array.from({ length: numNodes }, (_, i) => i);
  const rank = new Array(numNodes).fill(0);

  function find(x) {
    let root = x;
    while (parent[root] !== root) root = parent[root];
    while (parent[x] !== root) {
      const next = parent[x];
      parent[x] = root; // path compression
      x = next;
    }
    return root;
  }

  const mst = [];
  let totalWeight = 0;

  for (const edge of sorted) {
    const rootA = find(edge.a);
    const rootB = find(edge.b);
    if (rootA === rootB) continue; // would close a cycle — reject

    if (rank[rootA] < rank[rootB]) parent[rootA] = rootB;
    else if (rank[rootA] > rank[rootB]) parent[rootB] = rootA;
    else { parent[rootB] = rootA; rank[rootA]++; }

    mst.push(edge);
    totalWeight += edge.w;
    if (mst.length === numNodes - 1) break; // spanning tree complete
  }

  return { mst, totalWeight };
}

Pitfalls

Ties mean the MST isn't always unique. If two edges share the same weight, which one Kruskal happens to sort first can change which edges end up in the tree — though never the total weight, which is the same across every valid MST for a given graph. The demo's seven waypoints deliberately use ten distinct trail costs so there's exactly one right answer to point at; a real-world graph has no reason to avoid ties, and an implementation that needs one specific tie-broken answer (not just any minimum-weight tree) has to add an explicit tie-break rule on top — same caveat topological sort's Pitfalls section makes about non-unique orderings.

A disconnected graph doesn't get a spanning tree — it gets a spanning forest. If the input graph has no edges linking two of its pieces, no amount of edge-accepting will ever connect them, and the algorithm has no way to notice or complain: it just runs out of edges with fewer than numNodes - 1 accepted, having actually built the minimum spanning tree of each piece separately. Whether that's the right behavior or a silent bug depends entirely on the caller — worth checking for explicitly (e.g. mst.length === numNodes - 1) if a single connected tree was assumed.

The sort is the bottleneck, not the Union-Find calls. See Complexity below — this is why Kruskal is usually described by its sort cost rather than by how cheap the cycle check is.

Union-Find without its own optimizations degrades everything built on top of it. Skip path compression or union by rank in the find/union calls above and each one can cost up to O(n) instead of near-constant — see Union-Find's own Pitfalls for why both optimizations are needed together, not just one.

Measuring the sort's dominance

The Pitfall above asserts the sort dominates with no number attached. The reason isn't just "sorting is O(E log E) and Union-Find is near-constant" — it's that the main loop above stops early, the instant it has accepted numNodes - 1 edges (if (mst.length === numNodes - 1) break; in the reference implementation). On a random graph, most of a spanning tree's edges get found within the first few multiples of V entries off the front of the sorted list, because early on almost every node is still its own separate component and nearly any edge connects two of them — so the loop's real work tracks close to O(V) calls to find/union, almost independent of how large E actually is. The sort gets no equivalent shortcut: Kruskal needs the entire edge list in cheapest-first order before the loop can even start, so every one of the E edges gets sorted whether or not the loop ever reaches it. As E grows past V with the node count held fixed, the sort keeps getting more expensive while the loop's real cost stays nearly flat — the gap below is a function of density, not graph size.

Press "Build random graph & measure" to time the sort step against the Union-Find loop on a fresh random graph.

Each click builds a genuinely new random graph with real Math.random(), not a fixed seed, so the exact milliseconds — and the ratio between them — swing widely run to run at these sub-millisecond scales, where timer noise is a real fraction of what's being measured. Over two dozen clicks across 500, 2,000, and 5,000 nodes while writing this page, the swing was large within a density but the climb across densities never reversed: a tree-sized edge list (≈V) landed the sort anywhere from roughly 1×–20× the loop's time; ≈10×V edges, roughly 10×–75×; ≈100×V, roughly 175×–700×; and the densest preset, roughly 300×–1,700×. The same climb shows up at all three node counts — density drives the gap, not graph size — though the densest preset's exact edge count is capped at 1,000,000 regardless of V, so at 5,000 nodes it's only twice ≈100×V's edge count rather than ten times, and the two presets' ranges overlap more there than they do at 500 or 2,000 nodes.

Complexity

Time: O(E log E), dominated entirely by the initial sort — with E up to O(V²) for a dense graph, log E and log V differ by at most a constant factor, so this is equally often written O(E log V). The main loop itself is only O(E · α(V)) — E calls to Union-Find's near-constant find/union — which would be the whole story if the edges arrived pre-sorted; in practice the sort is what sets the ceiling. Space: O(V + E) — O(E) to hold the sorted edge list, O(V) for Union-Find's parent and rank arrays, same as Union-Find alone. The Reverse-Delete algorithm reaches the identical tree by sorting the same list the opposite direction and testing connectivity instead of components — a real asymptotic step down to O(E · (V + E)), not just a stylistic variation.

For a decision guide across all twelve of this site's Minimum Spanning Trees entries — when to reach for Kruskal's over Prim's or Borůvka's, and when the real question is bottleneck or second-best instead of minimum total — see Choosing a Minimum Spanning Tree Algorithm.