Reverse-Delete MST, in depth: the cycle property, a tested Python implementation, a traced example and why Kruskal wins

The algorithm

Given an undirected weighted graph G = (V, E):

REVERSE-DELETE(G):
    F = copy of E
    for e = (u, v) in E sorted by weight, heaviest first:
        remove e from F
        if u and v are no longer connected in (V, F):
            put e back                 # e is a bridge of F: the forest needs it
    return F

The rule is easy to state. An edge is removed only when some other path still joins its endpoints, so the number of connected components never changes. An edge that is kept was a bridge at the moment it was examined, and once an edge is a bridge it stays one, because later steps only delete edges. So at the end F has no cycles: every edge in a cycle would have been examined and found deletable. F spans each component and is acyclic, so it is a spanning forest. The question is why it is a minimum one.

Historically, the method appears in Joseph Kruskal's 1956 paper alongside the algorithm that carries his name, which is why some textbooks call it a variant of Kruskal.

Why it is correct

The tool is the cycle property: if an edge e is strictly the heaviest edge on some cycle C, then e is in no minimum spanning tree. Proof: suppose a spanning tree T contains e. Removing e splits T into two parts. The cycle C crosses between them at e, so it must cross back somewhere else, at an edge f not in T. Adding f reconnects the parts, giving a spanning tree lighter than T by w(e) - w(f) > 0. So T was not minimum.

Now take the invariant F contains a minimum spanning forest of G. It holds at the start, when F = E. Suppose it holds before e = (u, v) is examined, and e is deleted. Then u and v are still connected in F without e, so e closes a cycle in F. Every other edge on that cycle is either lighter than e (not yet examined) or heavier and already examined, and examined edges still in F are bridges, which cannot lie on a cycle. So e is the heaviest edge on a cycle of F, and an exchange argument like the one above shows that a minimum spanning forest inside F avoids e. The invariant survives, and at the end F is acyclic, so F is that minimum spanning forest.

With repeated weights, "heaviest" means heaviest under a fixed tie-break. Sort by the pair (weight, edge index) and every argument above goes through with strict inequalities. Different tie-breaks can return different trees, all of the same minimum weight.

Implementation and a test against Kruskal

A direct implementation uses breadth-first search for each connectivity check. It handles disconnected graphs, parallel edges and self-loops without special cases: a self-loop's endpoints are trivially connected, so it is always deleted.

from collections import defaultdict, deque

def connected(adj, alive, s, t):
    """BFS from s over live edges; True if t is reachable."""
    if s == t:
        return True
    seen, todo = {s}, deque([s])
    while todo:
        x = todo.popleft()
        for y, eid in adj[x]:
            if alive[eid] and y not in seen:
                if y == t:
                    return True
                seen.add(y)
                todo.append(y)
    return False

def reverse_delete(n, edges):
    """edges: list of (w, u, v). Returns indices of a minimum spanning forest."""
    adj = defaultdict(list)
    for i, (w, u, v) in enumerate(edges):
        adj[u].append((v, i))
        adj[v].append((u, i))
    alive = [True] * len(edges)
    order = sorted(range(len(edges)), key=lambda i: (edges[i][0], i), reverse=True)
    for i in order:
        w, u, v = edges[i]
        alive[i] = False                      # tentatively delete
        if not connected(adj, alive, u, v):   # it was a bridge
            alive[i] = True
    return sorted(i for i in range(len(edges)) if alive[i])

Test it against a trusted reference that uses the same tie-break. Kruskal with union-find (see union-find in depth) is the natural oracle:

def kruskal(n, edges):
    parent = list(range(n))
    def find(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]
            x = parent[x]
        return x
    keep = []
    for i in sorted(range(len(edges)), key=lambda i: (edges[i][0], i)):
        w, u, v = edges[i]
        ru, rv = find(u), find(v)
        if ru != rv:
            parent[ru] = rv
            keep.append(i)
    return sorted(keep)

import random
random.seed(7)
for _ in range(3000):
    n, wmax = random.randint(1, 9), random.choice([3, 100])
    edges = [(random.randint(1, wmax), random.randrange(n), random.randrange(n))
             for _ in range(random.randint(0, 20))]
    assert reverse_delete(n, edges) == kruskal(n, edges)

All 3,000 cases produce identical edge sets, including graphs with heavy weight ties (weights 1 to 3), self-loops, parallel edges and several components. Comparing edge sets is only valid because both sides break ties by index; with an arbitrary tie-break, compare total weights instead.

Worked example

Take vertices A to E and seven edges: A-B 1, B-D 2, B-C 3, A-C 4, C-D 5, D-E 6, C-E 7.

Four edges remain for five vertices, total weight 12, and Kruskal on the same graph picks the same four edges. Note step 2: D-E is the second heaviest edge but is kept, because E has no other neighbour after step 1. Reverse-delete does not avoid heavy edges; it avoids heavy edges that are redundant.

Cost, and how it relates to Kruskal

Sorting costs O(E log E). The naive loop runs one BFS of O(V + E) per edge, so the total is O(E(V + E)), which is quadratic in E for sparse graphs. Kruskal and Prim run in O(E log V). On a graph with a million edges, that is the difference between seconds and days.

Speeding it up means answering "are u and v still connected?" under deletions faster than a search. Fully dynamic connectivity structures do this in polylogarithmic amortised time per operation. Using Thorup's structure from 2000, the textbook bound commonly quoted for reverse-delete is O(E log V (log log V)^3). These structures are intricate and their constants are large; nobody implements them to compute an MST.

The practical speed-up is a cheaper test. Under a fixed tie-break, reverse-delete deletes e = (u, v) exactly when u and v are connected using edges lighter than e, since both algorithms return the unique MST for that order (the random test above checks the equivalence empirically). Answering that question for all edges at once, lightest first, with union-find is Kruskal's algorithm. Reverse-delete and Kruskal compute the same thing; one asks the question from above, the other from below.

When to use it

Use it, or its idea, in these situations:

• Pruning an existing network. When the input is a working network and the job is to remove the most expensive redundant links while keeping it connected, reverse-delete matches the problem. It is easy to stop early, for example after removing a budgeted number of links, leaving a connected network that is cheaper but still has some redundancy.
• Only a connectivity oracle is available. If the system can tell you whether two nodes are still reachable (a routing table, a simulator) but you cannot run union-find over the edges, reverse-delete needs nothing else.
• Maximum spanning tree. Reverse the order: delete the lightest non-bridge edge first.
• Constraints that are tested on the whole graph. If an edge may only be removed when a global property such as a diameter bound or 2-edge-connectivity still holds, swap the connectivity test for that property check. The result is no longer guaranteed minimum, but the shape of the algorithm is right.
• Teaching and verification. The cycle-property proof is the clearest one for MST, and a reverse-delete implementation is a good independent cross-check for an optimised Kruskal or Prim.

For plain MST on large inputs, use Kruskal on sparse edge lists and Prim on dense graphs or adjacency matrices. Bridge detection in one pass with Tarjan shows which edges any spanning tree must contain, but bridges change after each deletion, so it cannot replace the loop.

Variants: budgets, maximum trees and custom checks

Because the loop is so simple, the useful variants are one-line changes. The most practical is a budgeted pruner for an existing network: delete the costliest redundant links, but stop after a fixed number of deletions, so the result keeps some spare paths:

def prune(n, edges, budget, keep_connected=connected):
    """Delete up to `budget` of the heaviest redundant edges; return surviving indices."""
    adj = defaultdict(list)
    for i, (w, u, v) in enumerate(edges):
        adj[u].append((v, i))
        adj[v].append((u, i))
    alive = [True] * len(edges)
    deleted = 0
    for i in sorted(range(len(edges)), key=lambda i: (edges[i][0], i), reverse=True):
        if deleted == budget:
            break
        w, u, v = edges[i]
        alive[i] = False
        if keep_connected(adj, alive, u, v):
            deleted += 1                     # redundant: stays deleted
        else:
            alive[i] = True                  # bridge: put it back
    return [i for i in range(len(edges)) if alive[i]]

With budget at least E - V + c (where c is the number of components) the pruner returns the full minimum spanning forest; with a smaller budget it returns a connected subgraph that has shed its most expensive cycles first. For a maximum spanning tree, sort ascending instead of descending. To keep stronger guarantees, such as every vertex staying within some hop count of a root, pass a different keep_connected check. Be clear about what that costs: the cycle-property proof covers only the plain connectivity test, so a custom check gives a good heuristic, not a guaranteed optimum.

Failure modes

• Inconsistent tie-breaks. Sorting by weight alone with an unstable sort makes results vary between runs; tests that compare edge sets then fail at random. Sort by (weight, index).
• Checking connectivity with the edge still present. Forgetting to mark the edge dead before the search makes every edge look deletable, and the output is an empty forest.
• Global instead of endpoint connectivity. Testing "is the whole graph connected?" breaks on graphs that start disconnected: every edge looks like a bridge. Test whether u reaches v.
• Recursive DFS. A recursive search on a long path graph overflows Python's default recursion limit; use an explicit queue or stack.
• Expecting the naive version to scale. At 10⁵ edges the O(E(V + E)) loop is already billions of steps.

What to do next

1. Implement reverse_delete from the code above and run the random comparison against your own Kruskal.
2. Re-run the trace example by hand, then change C-E to weight 0.5 and predict the new tree before running it.
3. Write the proof of the cycle property in your own words; it is the core of every MST correctness argument.
4. Turn the algorithm into a maximum spanning tree and into a budgeted pruner that stops after k deletions.
5. Time the naive version against Kruskal at 10³, 10⁴ and 10⁵ edges to see the quadratic cost.
6. Read second-best MST for another algorithm built on cycle exchanges.