↩ back to Minimum Spanning Trees
Kruskal's, Prim's, and Borůvka's algorithms all minimize the same thing: the total weight of the spanning tree, every edge's cost added up. A minimum bottleneck spanning tree (MBST) minimizes something different — the weight of the single most expensive edge the tree is forced to use, ignoring everything else in the sum. The distinction matters whenever the sum isn't really the cost that matters: a courier network's end-to-end speed is capped by its single slowest required hop, not by adding every hop's time together; a set of pipes can only carry as much pressure as its narrowest required section can survive, no matter how wide all the others are. For those questions, a tree that's merely cheap on average is the wrong answer — what's wanted is the tree whose worst edge is as good as any spanning tree's worst edge can possibly be.
The two problems turn out to be closely related, just not identical. Every minimum spanning tree is automatically a minimum bottleneck spanning tree too — but, as the demo below shows on this site's own trail network, not every minimum bottleneck spanning tree is a minimum spanning tree. Minimizing the bottleneck is a strictly weaker requirement than minimizing the total, so it admits more solutions; the total-weight-minimal one is always among them, but so are others.
The same seven-waypoint trail network Kruskal's, Prim's, and Second-Best Spanning Tree all use — same nodes, same ten costs. Four of its trails are bridges: cut any one of them and the network splits in two, so every spanning tree needs all four, no choice involved. The other three trails — Basecamp–Spring, Spring–Saddle, Basecamp–Saddle — form the network's only triangle, so any spanning tree uses exactly two of those three and leaves one out. Click one of the three below to see the spanning tree that results from leaving it out; the remaining leftover trails (weight 8, 9, 10) never belong to any minimum bottleneck tree here at all — including any of them would need a costlier edge than the network's forced bottleneck already is.
Kruskal's own correctness argument rests on the cut property: the cheapest edge crossing any split of the nodes belongs to some MST. Minimum bottleneck trees rest on its usual counterpart, the cycle property: for any cycle in the graph, the single most expensive edge on that cycle is never needed to keep the graph connected as cheaply as possible, because every other edge on the cycle already offers some alternate route between its endpoints. Drop the priciest edge on every cycle and what's left is still connected, using nothing more expensive than necessary — which is exactly what Kruskal's own cycle-rejection rule already does on the way to building an MST, without ever being told to think about bottlenecks specifically. That's why Kruskal's output is always both a minimum spanning tree and a minimum bottleneck spanning tree at once.
But Kruskal's rule is stricter than bottleneck-minimality actually asks for. On this page's one triangle (Basecamp–Spring 2, Spring–Saddle 4, Basecamp–Saddle 6), Kruskal specifically drops the priciest edge, 6, because that's the one still uninspected — and therefore the one that closes the loop — once the sorted scan reaches it. Bottleneck-minimality doesn't care which of the three gets dropped: all three remaining trees keep the exact same maximum edge, 7 (Overlook–Summit, a bridge elsewhere in the network that every spanning tree is forced to include), so all three qualify as minimum bottleneck spanning trees. Only one of them — the one that drops 6, Kruskal's own answer — is also minimal on total weight (22, against 24 and 26 for the other two). Every MST is an MBST; the demo's other two candidates are the counterexample to the reverse.
Finding the bottleneck value itself needs nothing beyond Kruskal's own scan — the weight of the last edge accepted before the tree finishes spanning is the bottleneck, whether or not minimizing it was the actual goal. Checking whether some other candidate tree is also a valid MBST is a separate, cheap question: is it a spanning tree at all, and does every one of its edges stay at or under that same bottleneck value?
function bottleneckValue(numNodes, edges) {
// Kruskal's own scan — the last accepted edge's weight is the bottleneck.
const sorted = edges.slice().sort((x, y) => x.w - y.w);
const parent = Array.from({ length: numNodes }, (_, i) => i);
function find(x) {
let root = x;
while (parent[root] !== root) root = parent[root];
while (parent[x] !== root) { const next = parent[x]; parent[x] = root; x = next; }
return root;
}
let edgesUsed = 0, bottleneck = 0;
for (const edge of sorted) {
const rootA = find(edge.a), rootB = find(edge.b);
if (rootA === rootB) continue; // cycle — reject, same as Kruskal
parent[rootA] = rootB;
edgesUsed++;
bottleneck = edge.w;
if (edgesUsed === numNodes - 1) break;
}
return bottleneck;
}
function isValidMBST(numNodes, treeEdges, bottleneck) {
// A candidate is a valid MBST iff it's a spanning tree at all, and every
// edge in it stays at or under the known-minimal bottleneck value.
if (treeEdges.length !== numNodes - 1) return false;
if (treeEdges.some(e => e.w > bottleneck)) return false;
const parent = Array.from({ length: numNodes }, (_, i) => i);
function find(x) { let r = x; while (parent[r] !== r) r = parent[r]; return r; }
for (const e of treeEdges) {
const rootA = find(e.a), rootB = find(e.b);
if (rootA === rootB) return false; // cycle — not a tree
parent[rootA] = rootB;
}
return true; // numNodes - 1 acyclic edges among numNodes nodes = connected
}A valid MBST isn't automatically the MST — checking the bottleneck alone can't tell them
apart. All three trees in the demo above pass isValidMBST with the identical
bottleneck value, 7. Code that stops at "bottleneck matches, ship it" has a 2-in-3 chance of returning a
tree that's needlessly expensive overall on this page's own network (24 or 26 instead of 22) — verified
directly against the reference implementation above, not just reasoned about. If total weight matters at
all, minimizing the bottleneck first and then breaking ties on weight (which is exactly what Kruskal's
own scan already does for free) is the safe default, not an afterthought.
The bottleneck edge itself is not always safe to drop, even though it's the most expensive edge in the tree. It's tempting to assume the priciest edge in any tree is a candidate for being swapped out — but that's only true of edges sitting on a cycle. Overlook–Summit (7) sets this network's bottleneck and is also its single most expensive edge in every valid tree, yet it's a bridge, not part of any cycle: remove it from the graph entirely and Meadow and Summit split off into their own component, fully disconnected from the other five waypoints (checked directly against the network's adjacency, not assumed from the diagram). The cycle property only license dropping the max edge on a cycle — the max edge in the final tree overall is under no such guarantee, and here it happens to be the one edge nothing can route around.
Disconnected input has no spanning tree of either kind. Same failure mode as Kruskal's own pitfall — the scan just runs out of edges early, having built minimum bottleneck trees for each connected piece separately with no way to notice or complain on its own.
Time: O(E log E) the way this page computes it — Kruskal's own sort,
since that's the simplest way to get both the tree and its bottleneck value at once, and the reference
implementation above does no better. But bottleneck-minimality is a strictly weaker ask than
total-weight-minimality, and it turns out to be solvable in genuinely less time: repeatedly picking the
median remaining edge weight as a threshold, checking with one Union-Find pass whether the edges at or
under that threshold already connect the graph, and recursing into only the half of the weight range
that still needs narrowing (never re-sorting, never revisiting the half already ruled out) finds the
bottleneck value in expected O(E) — the same threshold-and-recurse shape as quickselect,
applied to edge weights instead of array elements. Camerini's 1978 algorithm is the standard reference
for this result; it earns its keep on graphs where E is large enough that skipping the sort
actually matters, which this page's ten-edge network is much too small to demonstrate.
Space: O(V + E) — the edge list plus Union-Find's parent array, same as
Kruskal alone.
For a decision guide across all ten of this site's Minimum Spanning Trees entries — including where this page fits once the real cost is a worst-hop cap rather than a sum — see Choosing a Minimum Spanning Tree Algorithm.