Cairn
guides · comparison, not a new algorithm

↩ back to Guides

Choosing a Minimum Spanning Tree Algorithm

The site's twelve Minimum Spanning Trees entries don't all answer the same question. Kruskal's, Prim's, Borůvka's, Reverse-Delete, Euclidean MST, Manhattan MST, and Randomized MST all build the same tree — the one minimizing total edge weight — by seven genuinely different mechanisms (Euclidean MST and Manhattan MST only when the input happens to be points in the plane rather than an arbitrary graph, each under its own distance metric). But Minimum Bottleneck Spanning Tree, Second-Best Spanning Tree, Minimum Spanning Tree Verification, Steiner Tree, and Minimum Arborescence aren't competing for the same job at all — they minimize something else, ask what comes after the minimum, check a candidate instead of building one, relax which nodes even need to be connected, or drop the assumption that edges even work both ways. So this guide splits in two: which of the first six builds the minimum spanning tree fastest for your input, and when one of the last five is actually the question you meant to ask instead.

Seven ways to build the same tree

Kruskal, Prim, and Borůvka never disagree on the answer — run all three on this site's own seven-waypoint trail network and every one lands on the identical tree, total weight 22, just by a different route. Reverse-Delete reaches the same tree too, mirror-image logic and all. Euclidean MST reaches it a fifth way, but only answers to a narrower input: it needs the vertices to be points in the plane with straight-line distance as weight, not just any weighted graph. Manhattan MST reaches it a sixth way, on that same narrower kind of input, but under a different metric entirely — L1 instead of L2 — which turns out to need its own geometric shortcut rather than letting Euclidean MST's own Delaunay triangulation be reused directly. Randomized MST reaches it a seventh way, on the same graph the first four use, by filtering the edge list against a random sample's own forest rather than sorting, growing a frontier, or running rounds. The choice among the first four is entirely about mechanism and cost, not correctness — two questions settle it, cheapest to check first, plus one honorable mention that's worth understanding but rarely worth reaching for; the fifth and sixth are each a single up-front question about what kind of input is actually in hand, and which metric it uses; the seventh is mostly of theoretical interest, covered on its own below.

Does the graph need to stay connected without one shared coordinator?

Borůvka's algorithm is the odd one out among the first three, and it settles the question outright when it applies: instead of one global sort (Kruskal) or one tree growing outward from a single seed (Prim), every component picks its own cheapest outgoing edge simultaneously, every round, with no shared state to coordinate — "the shape that turns out to matter most for parallel and distributed MST computation," per its own page. If the real constraint is computing the tree across independent workers with no central sequencer, Borůvka's round structure is built for exactly that; Kruskal's single global sort and Prim's single growing frontier both assume one process sees the whole picture. Its own pitfalls are the cost of that shape: without an explicit "did any component merge this round?" guard, a genuinely disconnected graph doesn't just return a partial answer the way Kruskal and Prim do — it spins forever, since no natural counter ever stops shrinking on its own.

Otherwise: is there already a natural starting point, or a flat sortable edge list?

Once distributed computation isn't the constraint, it's Kruskal against Prim, and with the right data structure on each side, both reach O(E log V) — Kruskal by sorting the whole edge list once and checking cycles with Union-Find, Prim by a binary-heap priority queue over the frontier. Prim's own page is explicit that its reference implementation doesn't use that heap — it swaps in a plain array, sorted and shifted on every pop, "for simplicity of the code shown, not simplicity of the real cost," costing O(E · V) worst case, "the same array-vs-heap tradeoff Dijkstra's algorithm makes." A production Prim needs the real heap to actually hit O(E log V); the array version is a demo simplification, not a deliberate tradeoff to reach for.

What genuinely differs is shape of access, not asymptotic cost: Kruskal's sort fits naturally when the edges already exist as a flat, sortable list with no adjacency structure needed up front. Prim's frontier fits naturally when there's already a specific place to start growing from — an existing hub node, or a network being extended outward from a facility that's already built — since it never has to look at the whole edge list at once, only whatever's currently reachable.

The other practical split is what a disconnected graph does to each of them, since neither one raises an error on its own. Kruskal's own pitfalls note it just runs out of edges early, having quietly built the minimum spanning tree of every piece separately — a spanning forest, not a single tree, recoverable by checking the accepted-edge count against numNodes - 1. Prim's own pitfalls are narrower: its frontier only ever sees the component containing the start node, so a disconnected graph makes it stop having built a tree for just that one piece, with no way to even notice the rest of the graph exists. Reaching for Kruskal when the caller needs to know about every component, or restarting Prim explicitly from a fresh node per undiscovered component, are the two ways to actually get full coverage.

Reverse-Delete: the same tree, a real step down in cost

Reverse-Delete answers the identical question — same cut-property tree, verified against the same trail network — by leaning on its mirror image, the cycle property, instead: start with every edge in the graph and delete the priciest ones first, unless deleting one would disconnect the network. It's genuinely instructive for that reason, the same role pigeonhole sort plays opposite counting sort — a second, correct route to the same answer via the opposite property — but its own Complexity section is explicit that it's "a real asymptotic step down" from the other three: O(E · (V + E)) naive, because every one of up to E deletion tests reruns a full connectivity scan from scratch, where Kruskal's Union-Find answers the equivalent question in near-constant time by keeping state across every prior edge instead of recomputing it. A production-grade version would need a dynamic connectivity structure to close that gap — this site's own Link-Cut Tree is exactly that, built to maintain a minimum spanning tree under an online mix of edge insertions and deletions, which Reverse-Delete's own one-shot, fixed-order deletion sweep doesn't need. Reach for Reverse-Delete to understand the cycle property, or when priciest-first deletion is a natural fit for data already in hand — not as the default practical pick among the four.

Race them yourself

The sections above state Kruskal's, Prim's, and Borůvka's complexity classes and name Reverse-Delete's own asymptotic step down — worth watching actually happen rather than taking on faith. This runs the exact reference implementations from Kruskal's algorithm, Prim's algorithm, Borůvka's algorithm, and Reverse-Delete, unmodified, in your own browser, against the same freshly generated random connected graph, timed with performance.now() — all four do real, heavy enough work here (a full sort, a priority queue rebuilt from scratch every pop, a from-scratch connectivity scan per edge tested) that timing is the honest measure, the same reason the comparison-sort race times instead of counting, unlike the lighter-weight search and shortest-path races above, which count operations instead because they're too fast at realistic sizes for timing to clear JIT noise.

Press "Run race" to time all four reference implementations on the same freshly generated graph.

Across every size and density combination above, two orderings hold with zero exceptions, measured over hundreds of trials: Kruskal always finishes before Prim, and Prim always finishes before Reverse-Delete. At 60 nodes, sparse, that's the whole story — all four land within a couple of milliseconds of each other, not enough of a gap to matter in practice. At 300 nodes, dense the gap stops being marginal: Prim's array-backed priority queue (its own page's documented demo simplification, not a deliberate tradeoff — see above) runs on the order of 100-200× slower than Kruskal at this size, and Reverse-Delete — paying for a full from-scratch connectivity scan on every one of up to E deletion tests — lands another 2-3× behind Prim again, exactly matching the asymptotic story above rather than just asserting it.

Kruskal vs. Borůvka is the one pairing here that doesn't settle into a fixed winner, and that's worth sitting with rather than smoothing over: both are formally the same O(E log V) class, and which one reports faster on any given click depends partly on how many times your browser has already run these exact functions in this tab, not just on the algorithm or the graph. At 300 nodes, dense, clicking Run race a few times in a row without changing anything else reliably settles into Borůvka finishing first — measured directly, dozens of times, in this exact page's own code — even though an early click can just as easily show Kruskal ahead instead. A directly observable case of JIT warmup state, not the algorithm or the input, deciding who wins a single race between two entries in the same complexity class. At smaller or sparser settings neither one ever reliably wins — the per-click gap is too small for warmup state to move it either way. All four agree on the total tree weight in every run; a mismatch would mean a real bug in this page's own code, not an expected outcome.

Euclidean MST: the same tree, when points are all you have

Euclidean MST answers the identical question too, but only when the input is narrower than an arbitrary graph: vertices that are literal points in the plane, with edge weight being straight-line distance. That narrower input carries geometric information a plain edge list throws away — the true minimum spanning tree is always a subgraph of the point set's own Delaunay triangulation, which has at most 3n - 6 edges, so ordinary Kruskal only needs to sort those instead of all n(n-1)/2 possible pairs. Its own pitfalls section is a caution against reaching for a cheaper-looking geometric shortcut instead: restricting to each point's k nearest neighbors looks like the same kind of pruning, but isn't guaranteed to contain the true MST at all — it silently produced the wrong total weight in about 21% of a 3,000-trial stress check, with no error anywhere in the run. Reach for this one only when the input is genuinely planar points with Euclidean weight; for any other weighted graph, it doesn't apply and one of the first four is the right tool.

Manhattan MST: the same tree again, under a different metric

Manhattan MST answers the identical question a third geometric way, on the same narrower kind of input as Euclidean MST — points in the plane — but priced by L1 (Manhattan) distance instead of straight-line distance. The tempting shortcut is to reuse Euclidean MST's own Delaunay triangulation and just re-weight its edges, but that doesn't reliably work: Delaunay triangulation is built entirely from Euclidean circumcircles, with no reference to which metric ends up pricing an edge, and its own page verified the mismatch is real — about 1% of a 5,000-trial stress check landed on the wrong total weight when Euclidean Delaunay was reused this way. The metric needs its own shortcut instead: split each point's neighborhood into 8 octants (each of the four quadrants cut again along its diagonal) and keep only the nearest point per octant as a candidate edge. Its own pitfalls section shows the natural simplification — 4 quadrants instead of 8 octants, one nearest neighbor each — silently drops a required edge on its own worked example, landing about 16 units over the true optimum with no error anywhere in the run. Reach for this one only when the input is planar points with Manhattan weight specifically; Euclidean MST's own shortcut doesn't transfer, and for any other weighted graph one of the first four is still the right tool.

A different question: the bottleneck, not the total

Minimum Bottleneck Spanning Tree isn't a fifth way to build the same tree — it minimizes the single most expensive edge the tree is forced to use, ignoring the sum entirely. That's the right question whenever the sum was never really the cost that mattered: a courier network's end-to-end speed is capped by its single slowest required hop, not by adding every hop together; a set of pipes can only carry as much pressure as its narrowest required section survives. Every minimum spanning tree is automatically a valid answer here too, but not the reverse — the page's own demo shows two other trees sharing the identical bottleneck value while costing more overall (24 and 26 against the true minimum's 22), and its pitfalls warn that the tree's single priciest edge isn't automatically droppable the way a cycle's priciest edge is — only a bridge can set the bottleneck and still be unremovable. If the answer needs to also be cheap overall, not just bottleneck-optimal, minimizing the bottleneck first and breaking ties on total weight is the safe default. Reach for this one when the real-world cost is a worst-hop limit, not a sum — and note its own page cites an O(E) expected-time algorithm (Camerini, 1978) that starts winning over Kruskal's sort at a measured 10–20 edges, plateauing around a 5× wall-clock speedup from a few thousand edges on.

A different question: what comes after the minimum

Second-Best Spanning Tree assumes the minimum spanning tree already exists — built by any of the first four — and asks what the next cheapest alternative is: a backup topology if a single link fails, or a check on how much cheaper the minimum tree really is than its closest rival. It doesn't need a search over every other spanning tree to answer that: adding any one leftover edge back into the minimum tree closes exactly one cycle, so the best replacement containing it is fixed — remove the single priciest edge already on that cycle. The true second-best is always exactly one such swap away, so checking every leftover edge's own best swap is exhaustive, not a heuristic. Reach for this one only once a minimum spanning tree is already in hand and the question has shifted from "build it" to "what's my next-best fallback."

A different question: is this already one, not building one

Minimum Spanning Tree Verification assumes even less than Second-Best Spanning Tree does — not that a minimum spanning tree already exists in hand, just that some candidate tree has been handed over, with no guarantee it's minimum at all. Checking that without rebuilding the answer from scratch turns out to need only one pass: the cycle property says a spanning tree is minimum exactly when no leftover edge is cheaper than the priciest tree edge on the path it would replace. Reach for this one when the tree to check is a given — read from a file, produced by a black-box process, or handed over by someone else's implementation — and confirming it's actually minimum is cheaper than distrusting it and running Kruskal's or Prim's over again.

A seventh way to build the same tree, trading a logarithm for randomness

Randomized MST is back to building the actual minimum spanning tree, not asking a different question — but the mechanism has nothing in common with the first six. Flip a coin on every edge, build the minimum spanning forest of just the half that survives, and reuse the exact cycle-property check Minimum Spanning Tree Verification already introduced to prove some fraction of the other edges can never be in any minimum spanning tree, no matter how the coins landed. Combined with two rounds of Borůvka-style contraction before each sample and a recursion this site's demo doesn't build, that gets to expected O(V + E) — genuinely faster than Kruskal's, Prim's, or Borůvka's own O(E log V), at least in expectation. In practice this is the one entry on this page to reach for out of curiosity rather than necessity: the constant factors and implementation complexity of the full recursive algorithm rarely pay for themselves against a well-implemented Kruskal's or Prim's unless E is large enough that a logarithm factor is genuinely the bottleneck. Reach for the other six first; reach for this one to understand how far a single cycle-property check can be pushed once it's no longer checking a finished tree.

A different question: connect only some of the nodes

Steiner Tree is the biggest departure from the rest of this page: it doesn't fix the same vertex set the other ten entries do at all. Only a required subset of nodes (terminals) has to end up connected; every other node is a free, unpriced waypoint if routing through it happens to be cheaper. That relaxation makes the general problem NP-hard — no polynomial algorithm is known to always find the true minimum — but a polynomial 2-approximation reuses the exact same tool the rest of this guide is about: treat the terminals as their own small complete graph, weighted by shortest-path distance in the original graph, and run Kruskal's algorithm on that instead of on the original graph directly. Reach for this one only when some nodes genuinely don't need to be reached — a required set of sites to connect within a larger network of optional relay points — not when every node in the graph has to end up in the tree, which is what the other ten entries already assume.

A different question: the edges only go one way

Minimum Arborescence is the only entry on this page where the other eleven don't just answer a different question — they don't apply at all. Every one of them assumes an undirected graph, where the cut property (the cheapest edge crossing any split of the vertices into two groups must belong to some minimum spanning tree) is what makes Kruskal's, Prim's, and Borůvka's each correct. A directed graph has no equivalent: a cut can be crossed by an edge pointed the "wrong" way for free, so the whole argument the first seven ways to build a tree lean on doesn't transfer. The question itself changes shape too — not a spanning tree at all, but a spanning arborescence rooted at a chosen vertex, where every other vertex has exactly one incoming edge and everything is reachable from the root by following edges forward. Chu-Liu/Edmonds' algorithm answers it by picking each vertex's cheapest incoming edge independently, then contracting and reweighting whenever that selection forms a cycle — the one genuinely new idea in this whole guide, with nothing analogous anywhere in the first eleven entries. Reach for this one only when edges are genuinely one-directional and the question is "reach every node as cheaply as possible from this one root" — for anything where an edge can be traversed either way, one of the other eleven is the right tool, not this one.

Side by side

EntryTimeSpaceMinimizesReach for it when
Kruskal's Algorithm O(E log E) O(V + E) total weight edges already exist as a flat, sortable list
Prim's Algorithm O(E log V) with a heap O(V + E) total weight a natural start node, or extending an existing network outward
Borůvka's Algorithm O(E log V) O(V + E) total weight parallel/distributed computation, no shared coordinator
Reverse-Delete Algorithm O(E · (V + E)) naive O(V + E) total weight learning the cycle property — not the practical default
Euclidean MST O(n log n) O(n) total weight vertices are points in the plane, weight is Euclidean distance
Manhattan MST O(n log n) O(n) total weight vertices are points in the plane, weight is Manhattan (L1) distance
Minimum Bottleneck Spanning Tree O(E log E) naive, O(E) optimal O(V + E) worst single edge the real cost is a worst-hop cap, not a sum
Second-Best Spanning Tree O(V · E) naive O(V + E) next-cheapest total, given the minimum need a backup topology once the MST already exists
Minimum Spanning Tree Verification O(V · E) naive O(V + E) nothing — checks, doesn't build a candidate tree already exists and needs confirming, not building
Randomized MST (Karger–Klein–Tarjan) expected O(V + E) O(V + E) total weight curiosity, or E large enough that shaving a logarithm genuinely matters
Steiner Tree O(k · E log V), NP-hard exact O(V + E + k²) total weight over a required subset only some nodes are optional waypoints, not every node needs connecting
Minimum Arborescence O(V · E) naive O(V · E) worst case total weight, rooted directed out-tree edges are one-directional — none of the other eleven even apply