The site's ten Minimum Spanning Trees entries don't all answer the same question. Kruskal's, Prim's, Borůvka's, Reverse-Delete, Euclidean MST, and Randomized MST all build the same tree — the one minimizing total edge weight — by six genuinely different mechanisms (Euclidean MST only when the input happens to be points in the plane rather than an arbitrary graph). But Minimum Bottleneck Spanning Tree, Second-Best Spanning Tree, Minimum Spanning Tree Verification, and Steiner Tree 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, or relax which nodes even need to be connected. 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 four is actually the question you meant to ask instead.
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 distance as weight, not just any weighted graph. Randomized MST reaches it a sixth 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 is a single up-front question about what kind of input is actually in hand; the sixth is mostly of theoretical interest, covered on its own below.
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.
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 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, which this page doesn't build. Reach for
it 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.
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.
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) once E is large enough that skipping Kruskal's sort actually pays off.
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."
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.
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 five. 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 five 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.
Steiner Tree is the biggest departure from the rest of this page: it doesn't fix the same vertex set the other nine 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 nine entries already assume.
| Entry | Time | Space | Minimizes | Reach 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 |
| 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 |