↩ back to Minimum Spanning Trees
Kruskal's, Prim's, Borůvka's, and Reverse-Delete all answer the same question — what's the cheapest spanning tree? This page asks a different one: given that tree, what's the next cheapest? Not a tuning knob on the same algorithm, a genuinely different problem — a network operator who already built the minimum spanning tree still wants to know its closest rival, as a backup topology if one link fails, or as a check on just how much cheaper the minimum tree really is than any alternative. The answer turns out not to need a search over every other spanning tree at all: the second-best is always reachable from the minimum spanning tree by swapping out exactly one edge for exactly one other.
The same seven-waypoint trail network every other Minimum Spanning Trees page uses — same nodes, same ten costs, same minimum spanning tree (solid orange, total weight 22) that Kruskal's, Prim's, and Borůvka's pages all reach. The four leftover trails (dashed grey) are exactly the edges the minimum tree left out. Click one below to see what happens if it gets added back in: adding any leftover edge to a tree that already connects every waypoint closes exactly one cycle, so exactly one tree edge on that cycle has to leave to restore a tree — and the demo highlights the one that leaves the smallest possible bill behind, the single priciest edge on the path between the clicked edge's two endpoints (shown in red).
The minimum spanning tree already connects all seven waypoints, so adding any one more edge — say,
a leftover trail between waypoints u and v — closes exactly one cycle: the new edge
plus the single existing tree path between u and v. To get back to a valid spanning
tree, exactly one edge on that cycle has to go. Removing the edge that was just added undoes the whole
swap and changes nothing, so the only edges worth considering for removal are the ones already on the
tree path. Among those, removing the most expensive one leaves the smallest possible
total behind — the new total is always (old total) − (removed edge) + (added edge), and
that's minimized by making the subtracted term as large as it can be. So for any one leftover edge, its
single best possible swap is fixed: remove the priciest edge on the tree path between its endpoints.
That gives one candidate replacement tree per leftover edge. The second-best spanning tree overall is the cheapest of those candidates — because any spanning tree that isn't the minimum one can be turned into the minimum one by a sequence of single-edge swaps that never dips below the minimum tree's own weight partway through (a standard fact about spanning trees, confirmed here against a brute-force scan of all 210 six-edge subsets of the network's ten edges, which turns up exactly one tree at weight 22 and the true second-best at 24, with nothing in between). If the real second-best needed two or more swaps to reach, the tree sitting one swap into that sequence would already be a valid spanning tree with weight strictly between the minimum and the claimed second-best — which would make it the actual second-best instead, a contradiction. So the true second-best is always exactly one swap away, and checking all four possible single swaps here is exhaustive, not a heuristic.
Builds on Kruskal's own MST output — same sort, same Union-Find, from Kruskal's page — then walks the tree once per leftover edge:
function treePath(treeAdj, u, v) {
// treeAdj: adjacency list built from MST edges only. Returns the edges
// on the unique tree path from u to v, since a tree has exactly one.
const parent = new Array(treeAdj.length).fill(null);
const visited = new Array(treeAdj.length).fill(false);
const queue = [u];
visited[u] = true;
while (queue.length) {
const cur = queue.shift();
if (cur === v) break;
for (const { to, edge } of treeAdj[cur]) {
if (!visited[to]) { visited[to] = true; parent[to] = { node: cur, edge }; queue.push(to); }
}
}
const path = [];
for (let cur = v; cur !== u; cur = parent[cur].node) path.push(parent[cur].edge);
return path;
}
function secondBestMST(numNodes, edges, mst, mstTotal) {
const inTree = new Set(mst);
const treeAdj = Array.from({ length: numNodes }, () => []);
for (const e of mst) {
treeAdj[e.a].push({ to: e.b, edge: e });
treeAdj[e.b].push({ to: e.a, edge: e });
}
let best = null;
for (const e of edges) {
if (inTree.has(e)) continue; // only leftover edges are candidates
const path = treePath(treeAdj, e.a, e.b);
const maxEdge = path.reduce((m, pe) => (pe.w > m.w ? pe : m), path[0]);
const total = mstTotal - maxEdge.w + e.w;
if (!best || total < best.total) best = { added: e, removed: maxEdge, total };
}
return best; // the cheapest single swap = the second-best spanning tree
}Forgetting to exclude tree edges from the candidate loop silently reports the minimum tree
itself as its own second-best. A tree edge's two endpoints are directly connected by that
exact edge, so the "path" between them is just the edge itself — feed a tree edge through the same
swap formula and the max edge on its one-edge path is the edge itself, giving total = 22 − 1 + 1
= 22 for the Saddle–Overlook edge specifically (checked against the real shipped script): the
correct MST weight, reported as if it were a distinct cheaper alternative. It doesn't crash and the
number even looks plausible — it's exactly the minimum weight, which is a real spanning tree weight,
just not a second one. The inTree.has(e) check above exists specifically to rule
this out.
Removing the first edge found on the path instead of the most expensive one still produces
a valid spanning tree for every candidate — and gets the overall answer wrong anyway, not just one
candidate's number. Run that variant against this page's own network: the Basecamp–Saddle
candidate's path is Basecamp–Spring (2) then Spring–Saddle (4); removing whichever one the traversal
happens to visit first (Basecamp–Spring) instead of the true max gives 22 − 2 + 6 = 26
instead of the correct 24. That one candidate's number is now wrong — but by coincidence
the Ridge–Saddle candidate's first-visited path edge and its true max edge are the same edge, so its
number (25) doesn't change. The buggy version's cheapest candidate is now Ridge–Saddle at 25 instead of
the true winner, Basecamp–Saddle at 24 — a different edge, a different total, both checked against the
real shipped script through a fake-DOM harness, not just reasoned about.
Time: O(V · E) for the naive version this page implements — building
the minimum spanning tree costs Kruskal's own O(E log E), but the demo's own walk after
that dominates: up to E − V + 1 leftover edges, each paying a fresh O(V)
breadth-first walk across the tree to find its path. Production implementations answer many such
path-max queries against the same fixed tree with a Binary Lifting structure instead — each node
precomputes its 2^k-step ancestors and the max edge weight along each jump, built once in
O(V log V), after which any single path-max query costs O(log V) — turning
this page's O(V · E) into O((V + E) log V) overall. Seven waypoints and ten
edges are far too small for that extra machinery to earn its keep, so this demo doesn't build it — see
Binary Lifting's own worked path-max
example for the extension in full, verified against this exact technique.
Space: O(V + E) — the tree's adjacency list plus the edge list itself.
For a decision guide across all ten of this site's Minimum Spanning Trees entries — including where this page fits once a minimum spanning tree already exists — see Choosing a Minimum Spanning Tree Algorithm.