Reverse-Delete MST

Reverse-Delete is the mirror image of the usual minimum-spanning-tree algorithms. Instead of adding the cheapest edges that keep the tree growing, it removes the most expensive edges that the graph can live without.

The slow way first

You could enumerate every subset of edges, throw away the ones that are not spanning trees, and pick the cheapest. The number of subsets is exponential, so that is hopeless for anything but a tiny graph.

The question to ask: which edges are obviously safe to throw away? A heavy edge is a waste as long as the graph stays connected without it. So work from the most expensive edge downward and delete greedily.

The idea: delete the heaviest redundant edges

Sort the edges from heaviest to lightest. Walk that list. For each edge, ask: if I remove it, is the graph still connected? If yes, the edge was redundant — there was a cheaper way around it — so delete it. If no, removing it would split the graph, which means it is a bridge we are forced to keep.

What survives this pruning is exactly a minimum spanning tree. We always removed the most expensive edge we possibly could, so the cheapest necessary edges are the ones left standing.

Walk through it

Step through the animation. The five edges are tried in weight order 5, 4, 3, 2, 1. Edges B-C (5) and C-D (4) fade out — the graph stays connected without them. Then B-D, A-C, and A-B each turn out to be bridges: removing any of them would isolate a vertex, so they are kept, building the total up to 6.

Pseudocode

sort edges from heaviest to lightest
total = 0
for each edge (u, v, w) in that order:
    temporarily remove (u, v, w)
    if the graph is still connected:
        keep it removed        # redundant edge
    else:
        put it back            # bridge — required
        total = total + w
return total

The Python solution

def reverse_delete(n, edges):       # edges: list of (u, v, w)
    edges.sort(key=lambda e: e[2], reverse=True)
    total = 0
    for u, v, w in edges:
        without = [e for e in edges if e != (u, v, w)]
        if connected(n, without):
            edges = without             # redundant — drop it
        else:
            total += w                  # bridge — keep it
    return total

• We sort with reverse=True so the heaviest edge comes first.
• For each edge we build without, the edge set minus the current edge, and ask whether that smaller graph still connects all n vertices.
• connected(...) is a standard graph search (BFS/DFS or union-find) that returns True when every vertex is reachable.
• If it is still connected, the edge was redundant — we commit to the deletion by setting edges = without.
• Otherwise the edge is a bridge: we leave it in and add its weight w to total.

Complexity

The connectivity check inside the loop is what makes this slower than Kruskal or Prim. It is prized for being conceptually clean and for working when you literally want the edges you can afford to delete.

When this pattern shows up

Practice