↩ back to Minimum Spanning Trees
Kruskal's, Prim's, and Borůvka's algorithms all build a minimum spanning tree one accepted edge at a time, starting from nothing. Reverse-Delete does the opposite: start with every edge already in the graph, sort them priciest first, and walk the list asking one question of each — "if I deleted this edge right now, would the network still hold together?" If yes, delete it; that edge was never load-bearing, some cheaper path already connects its two ends. If no, it's a bridge — keep it forever. Where the other three algorithms all lean on the cut property (the cheapest edge crossing any split must belong to some MST), Reverse-Delete leans on its mirror image, the cycle property — and still lands on the exact same tree.
The same seven-waypoint trail network every other Minimum Spanning Trees page uses — same nodes, same ten edge costs. Press Step or Run: each step tests one edge, priciest remaining first. A black-bordered pair of nodes is the edge under test; an edge that turns dashed and struck through was just deleted (redundant — the rest of the network still reaches it); an edge that turns solid orange was just confirmed as a bridge and locked in for good. By the end, six edges survive out of the original ten — the identical minimum spanning tree, and the identical total weight of 22, that Kruskal's, Prim's, and Borůvka's pages all reach by building up instead of tearing down.
The cycle property is the mirror image of the cut property Kruskal's page explains: for any cycle in the graph, the single most expensive edge on that cycle cannot belong to any minimum spanning tree (if some tree did include it, swapping it out for any other edge on the cycle would only make that tree cheaper or leave it unchanged — never worse, since every other edge on the cycle costs the same or less). Deleting priciest-first is exactly how this demo puts that guarantee to use: when an edge is tested, every edge heavier than it has already been decided, so if the graph stays connected without it, this edge is — among everything still present — the most expensive edge on whatever cycle just proved it redundant. The cycle property says it was never going to be in the MST regardless of what happens to the cheaper edges still waiting their turn, so deleting it immediately is safe, not just a good guess.
Contrast with an edge the demo keeps: if deleting it would disconnect the network, then by definition no cycle currently contains it — it's a bridge, the only path left between whatever it connects. A bridge is, trivially, the cheapest (and only) edge crossing the cut it sits on, so the cut property Kruskal's and Prim's pages rely on justifies keeping it too. Every accepted edge in this demo is simultaneously "the max on no live cycle" and "the min across some cut" — the two properties aren't competing explanations, they're two names for the same set of safe edges, approached from opposite directions.
Matches the demo above one for one, just without the yield points that show every
test and its outcome:
function isConnected(numNodes, edges) {
const adj = Array.from({ length: numNodes }, () => []);
for (const e of edges) { adj[e.a].push(e.b); adj[e.b].push(e.a); }
const seen = new Array(numNodes).fill(false);
const stack = [0];
seen[0] = true;
let count = 1;
while (stack.length) {
const u = stack.pop();
for (const v of adj[u]) {
if (!seen[v]) { seen[v] = true; count++; stack.push(v); }
}
}
return count === numNodes;
}
function reverseDeleteMST(numNodes, edges) {
// edges: [{ a, b, w }, ...] — undirected, weight w
const sorted = edges.slice().sort((x, y) => y.w - x.w); // priciest first
let remaining = edges.slice();
for (const edge of sorted) {
const without = remaining.filter(e => e !== edge); // test WITHOUT this edge
if (isConnected(numNodes, without)) {
remaining = without; // redundant — delete it
}
// else: it's a bridge — leave it in `remaining`, keep going
}
return remaining; // the minimum spanning tree
}Processing order isn't a tuning knob, it's load-bearing — cheapest-first doesn't just find a worse answer, it tends to find close to the worst one. Running this page's own generator with the sort direction flipped (cheapest-first instead of priciest-first) on the exact same ten-edge network produces a real, checked result: a valid spanning tree — six edges, fully connected — but with total weight 45 instead of 22, more than double the true minimum, keeping the four most expensive edges in the network (weights 5, 6, 7, 8, 9, 10 minus whichever one test fails first) instead of the four cheapest. The mechanism is direct: this variant tests whether each cheap edge is redundant while the graph is still nearly complete, so cheap edges — usually the ones a correct MST most wants to keep — get deleted early just because some pricier detour happens to still be available at that point. The cycle property above only licenses deleting the single most expensive edge on a cycle; testing cheap edges first has no such license and the demo's own numbers show the gap it opens up.
Forgetting to exclude the edge under test before checking connectivity produces a result that looks plausible — six edges, the right count for a spanning tree — while being silently wrong. The correct check asks "is the graph connected without this edge?" A tempting shortcut checks the graph as it currently stands, edge still included instead — which is almost always "yes" early on, so it deletes the edge anyway without ever really testing it. Run that broken variant against this page's own network and it ends with exactly six edges remaining, the same count a correct run produces, but actually disconnected — checked directly by running a reachability scan against the six leftover edges, which reaches only some of the seven waypoints, not all of them. Six edges is necessary for a spanning tree of seven nodes but nowhere near sufficient; this is a bug that a count-only sanity check can't catch, only an actual connectivity check on the final result can.
Ties mean the MST isn't always unique — the same caveat Kruskal's and Borůvka's Pitfalls sections make. This network's ten distinct trail costs sidestep the question entirely; with a tie, which of the tied edges survives a connectivity test first can depend on how the sort breaks the tie, though the total weight of any valid MST for a given graph never changes.
Time: O(E · (V + E)) for the naive version this page implements —
sorting the edges costs O(E log E), but that's dominated by the main loop: up to
E edges tested, and each test reruns a full O(V + E) reachability scan from
scratch. That's a real asymptotic step down from
Kruskal's near-O(E α(V)) Union-Find checks or
Borůvka's O(E log V) — Reverse-Delete's per-edge
question ("does deleting this disconnect the graph?") is intrinsically more expensive to answer than
"are these two nodes already in the same component?", which Union-Find answers in near-constant time
by maintaining state across every prior edge instead of recomputing reachability fresh each time. A
production implementation would reach for a dynamic connectivity structure to answer each test
faster than a full rescan; this page's demo, sized for seven waypoints, doesn't need one to make the
point. Space: O(V + E) — an adjacency list rebuilt for each
connectivity check, plus O(E) to hold the edge list itself.
For a decision guide across all ten of this site's Minimum Spanning Trees entries — including why Reverse-Delete is worth understanding for the cycle property but rarely the practical pick over Kruskal's, Prim's, or Borůvka's — see Choosing a Minimum Spanning Tree Algorithm.