Reverse-delete algorithm
The reverse-delete algorithm is a greedy algorithm for finding a minimum spanning tree (MST) in a connected, undirected graph with non-negative edge weights. First described by Joseph Kruskal in 1956, it operates by starting with the full set of edges and iteratively removing the highest-weight edges that do not disconnect the graph, yielding a spanning tree of minimum total weight.[1]
Unlike Kruskal's algorithm, which constructs the MST by adding the lowest-weight edges without forming cycles, the reverse-delete algorithm begins with all edges and prunes them in decreasing order of weight, skipping edges whose removal would disconnect the graph (i.e., bridges in the current subgraph). This approach relies on the cycle property of MSTs: the maximum-weight edge in any cycle cannot belong to an MST.[2][3]
The algorithm's correctness stems from the greedy choice properties shared with other MST algorithms, ensuring the result is minimal while maintaining connectivity. Though asymptotically comparable to Kruskal's in efficient implementations, it is less commonly used due to the challenges in performing repeated connectivity tests, particularly on dense graphs.[4] The method illustrates the duality in MST construction and provides insight into greedy optimization in graphs.
Introduction
Overview
The reverse-delete algorithm is a greedy method for constructing a minimum spanning tree (MST) in a connected, undirected graph with weighted edges, beginning with the full set of edges and iteratively removing the heaviest edges that do not disconnect the graph.[4][5] This approach contrasts with additive methods like Kruskal's algorithm by focusing on deletion rather than insertion to build the spanning tree.[4]
Key prerequisites include an undirected graph G = (V, E), where vertices V represent nodes and edges E connect pairs of vertices with assigned non-negative weights indicating costs.[5] A spanning tree is defined as a subgraph that connects all vertices without cycles, and the minimum spanning tree is the one among all possible spanning trees with the smallest total edge weight.[4] The algorithm assumes the graph is connected to ensure a spanning tree exists.[5]
The purpose of the reverse-delete algorithm is to efficiently compute an MST by pruning high-cost edges while preserving graph connectivity, leveraging properties such as the cycle property—which states that the heaviest edge in any cycle cannot belong to an MST—to guarantee optimality.[4] At a high level, the process involves sorting all edges in decreasing order of weight and then sequentially attempting to remove each edge, skipping removal only if it would disconnect the graph (e.g., via a connectivity check such as DFS or BFS traversal).[5][6] This results in a tree that spans all vertices with minimal total weight.[4]
Relation to Minimum Spanning Trees
The reverse-delete algorithm exhibits a strong duality to Kruskal's algorithm in the context of minimum spanning trees (MSTs). While Kruskal's algorithm constructs an MST by sorting edges in increasing order of weight and adding the lightest edges that do not form cycles, the reverse-delete algorithm inverts this process by sorting edges in decreasing order of weight and removing the heaviest edges that do not disconnect the graph. This mirroring approach ensures that both algorithms greedily select edges based on the cycle property of MSTs, where the heaviest edge in any cycle cannot belong to an MST, leading to equivalent outcomes when applied to the same graph.[3][5]
The output of the reverse-delete algorithm is guaranteed to be an MST, possessing the essential properties of being acyclic, connected, and of minimal total edge weight, identical to those produced by Kruskal's or Prim's algorithms. By starting from the complete graph and iteratively deleting only "unsafe" heavy edges—those whose removal maintains connectivity—the algorithm preserves a spanning tree while minimizing weight through adherence to the cut property, which ensures that no lighter edge is overlooked in the final structure. This results in a tree that spans all vertices with the lowest possible cost, verifiable through the exchange arguments underlying MST optimality.[4][5]
In comparison to Prim's algorithm, which builds an MST greedily from a starting vertex by repeatedly adding the minimum-weight edge connecting the growing tree to an unvisited vertex, the reverse-delete algorithm operates globally across all edges without a designated starting point, beginning instead from the full edge set. This global perspective aligns it more closely with Kruskal's in terms of efficiency, both achieving near-linear time with appropriate data structures, though reverse-delete's initial complete graph assumption suits dense graphs particularly well.[3][4]
The reverse-delete algorithm finds application in network design scenarios where a full topology is initially available, such as telecommunications or transportation systems, allowing for the systematic removal of redundant high-cost links to achieve minimal connectivity. For instance, in optimizing cable layouts or road networks, it facilitates pruning expensive connections while ensuring the remaining infrastructure remains spanning and cost-effective.[4]
Algorithm
Steps
The reverse-delete algorithm operates on a connected, undirected graph G = (V, E) with non-negative edge weights, beginning with the full set of edges E that spans all vertices V.[7][5]
All edges are first sorted in non-increasing order of their weights, so the heaviest edges are considered first for potential deletion.[3][4]
The algorithm then proceeds iteratively through this sorted list: for each edge e = (u, v), it determines whether deleting e from the current graph would increase the number of connected components (i.e., disconnect the graph).[7][5] This connectivity check can be performed using depth-first search (DFS) or breadth-first search (BFS) on the graph induced by the current edge set excluding e, to verify if u and v remain connected.
If deletion of e maintains connectivity, the edge is removed; otherwise, it is retained.[3][4]
This deletion process continues until exactly |V| - 1 edges remain, ensuring the final subgraph is a tree that connects all vertices and serves as the minimum spanning tree.[7][5]
Pseudocode
The reverse-delete algorithm is typically presented in pseudocode that starts with the complete set of edges and iteratively removes the heaviest edge provided that doing so does not disconnect the graph. This approach leverages the cycle property of minimum spanning trees, ensuring that removed edges are the heaviest in some cycle. The following pseudocode outlines the process, assuming the input is a connected, undirected graph G = (V, E) with edge weights.[4]
REVERSE-DELETE(G):
1 T ← E // Start with all edges; T will become the MST edges
2 Sort the edges in T in decreasing order of weight
3 for each edge e ∈ T (in decreasing weight order):
4 if T − {e} is still [connected](/page/Connectivity):
5 T ← T − {e} // Remove e safely
6 return T
REVERSE-DELETE(G):
1 T ← E // Start with all edges; T will become the MST edges
2 Sort the edges in T in decreasing order of weight
3 for each edge e ∈ T (in decreasing weight order):
4 if T − {e} is still [connected](/page/Connectivity):
5 T ← T − {e} // Remove e safely
6 return T
In this pseudocode, the edges are represented as a list of triples (u, v, w), where u and v are vertices and w is the edge weight, facilitating sorting in descending order of w. The connectivity check in line 4 can be implemented using depth-first search (DFS) or breadth-first search (BFS) on the graph induced by T − {e}, which verifies if the endpoints of e remain in the same connected component. For improved efficiency in practice, optimizations such as preprocessing or specialized data structures may be used, though the basic version relies on traversal. The Union-Find data structure, equipped with path compression and union-by-rank, can support efficient connectivity queries in related greedy MST algorithms like Kruskal's, achieving nearly linear time overall, but for reverse-delete, the deletion aspect requires careful handling of component maintenance.[4][8]
The algorithm assumes the input graph is connected; if not, it can be adapted to produce a minimum spanning forest by applying the process to each component separately. For graphs with equal edge weights, the algorithm remains correct regardless of tie-breaking, as stable sorting is not required—the greedy choice property ensures an optimal result. Isolated vertices or empty graphs are handled trivially, with no edges in the output.[4]
Worked Example
Graph Setup
To illustrate the reverse-delete algorithm, consider a simple undirected, connected, edge-weighted graph G = (V, E) with vertex set V = \{A, B, C, D\} and edge set E consisting of six edges with positive integer weights, as shown in the table below. This setup provides more edges than the minimum required for a spanning tree (|V| - 1 = 3), enabling the deletion process while maintaining connectivity.
| Edge | Weight |
|---|
| A-B | 1 |
| A-C | 3 |
| A-D | 4 |
| B-C | 2 |
| B-D | 5 |
| C-D | 1 |
Iteration Details
The reverse-delete algorithm proceeds by considering edges in decreasing order of weight, attempting to delete each one if doing so maintains the graph's connectivity. For the example graph with vertices A, B, C, and D, the edges sorted in decreasing weight order are: BD (weight 5), AD (4), AC (3), BC (2), AB (1), and CD (1). Initially, the graph is fully connected with all six edges, forming a single connected component.
The first edge considered is BD (weight 5). Deleting BD leaves alternative paths between B and D, such as B-A-D or B-C-D, preserving connectivity in one component. Thus, BD is deleted, and the remaining graph consists of edges AD, AC, BC, AB, and CD. Next, AD (weight 4) is considered; its deletion still connects A and D via A-C-D or A-B-C-D, so AD is removed, leaving AC, BC, AB, and CD with one connected component.
Continuing, AC (weight 3) is evaluated; removing it connects A and C via A-B-C, maintaining a single component with edges BC, AB, and CD. The graph now forms a path A-B-C-D. The next edge, BC (weight 2), is tested for deletion; removing BC would split the graph into two components—A-B and C-D—violating connectivity, so BC is retained. At this stage, the intermediate structure is a chain connecting all vertices through AB, BC, and CD.
For AB (weight 1), deletion would isolate A from the rest (B-C-D via BC and CD), creating two components, so AB is kept. Similarly, removing CD (weight 1) would isolate D from A-B-C, disconnecting the graph, so CD is retained. No further deletions are possible, resulting in the minimum spanning tree consisting of edges AB (1), BC (2), and CD (1), with a total weight of 4. This tree spans all vertices without cycles, as depicted by the path A-B-C-D.
| Step | Edge Considered (Weight) | Deletion Decision | Components After Attempt | Remaining Edges |
|---|
| 1 | BD (5) | Deleted | 1 | AD, AC, BC, AB, CD |
| 2 | AD (4) | Deleted | 1 | AC, BC, AB, CD |
| 3 | AC (3) | Deleted | 1 | BC, AB, CD |
| 4 | BC (2) | Retained | 1 (if deleted: 2) | BC, AB, CD |
| 5 | AB (1) | Retained | 1 (if deleted: 2) | BC, AB, CD |
| 6 | CD (1) | Retained | 1 (if deleted: 2) | BC, AB, CD |
Complexity
Time Complexity
The reverse-delete algorithm has a time complexity of O(E \log E + E(V + E)), where E is the number of edges and V is the number of vertices, dominated by the connectivity checks in dense graphs.[6]
The edges are first sorted by weight in decreasing order, which takes O(E \log E) time using a comparison-based sorting algorithm such as merge sort or heap sort.[4] Subsequently, the algorithm iterates over the sorted edges, and for each edge, it performs a connectivity check to determine if removal would disconnect the graph, typically using depth-first search (DFS) or breadth-first search (BFS), each taking O(V + E) time, leading to a total of O(E(V + E)) for all checks.[6]
In the worst case, for dense graphs where E \approx V^2, the time complexity is O(V^3); the analysis assumes the input graph is connected, as the algorithm produces a minimum spanning forest otherwise.[4]
This time complexity is worse than Kruskal's algorithm, which runs in O(E \log V) using Union-Find, and the naive implementation of Prim's algorithm, which runs in O(V^2) time using an adjacency matrix, especially in sparse graphs where E \ll V^2. The reverse-delete algorithm is thus less practical for large graphs due to the repeated full-graph traversals.[6][9]
Space Complexity
The reverse-delete algorithm exhibits an overall space complexity of O(V + E), which is linear with respect to the input size of the graph, where V denotes the number of vertices and E the number of edges.[6]
This bound arises from the primary components of its data structures: the graph is typically represented using an adjacency list, consuming O(V + E) space to store vertices and their incident edges; an additional edge list is required for sorting the edges in decreasing order of weight, occupying O(E) space.[10][6]
To determine whether deleting an edge would disconnect the graph, the algorithm employs connectivity checks, often via depth-first search (DFS) or breadth-first search (BFS), which utilize auxiliary arrays such as a visited vector of size O(V) or a recursion stack bounded by O(V) in the worst case.[6]
While the adjacency list permits in-place modifications during edge deletions to avoid extra graph copies, the sorting step inevitably demands temporary O(E) space for the edge list, as edges must be extracted and ordered independently of the original representation.[10]
In comparison to Prim's algorithm, which can achieve O(V) auxiliary space beyond the input in optimized implementations using priority queues without full edge storage, the reverse-delete approach may require more memory due to the explicit handling of all edges upfront, though it performs well for sparse graphs where E ≈ V.[11]
Correctness
Spanning Tree Guarantee
The reverse-delete algorithm operates on a connected, undirected graph G = (V, E) and guarantees the production of a spanning tree by preserving connectivity while systematically reducing the number of edges until the tree condition is met. The process begins with the full edge set E, which spans all vertices |V| and maintains connectivity. Edges are considered for deletion in decreasing order of weight, but an edge is removed only if its deletion does not disconnect the graph, meaning the endpoints remain in the same connected component via alternative paths. This condition is efficiently verified using a Union-Find data structure, which tracks components and confirms that removing the edge would not increase the number of components beyond one.[3][4] By construction, the subgraph remains connected after each deletion, as no removal ever splits the graph into multiple components.[12][5]
The algorithm terminates when no further edges can be deleted without disconnecting the graph, at which point every remaining edge is a bridge essential for connectivity. This stopping condition ensures the final subgraph has exactly |V| - 1 edges, as the process eliminates redundant edges while preserving the spanning property. To formalize this, consider an induction on the number of edges: the initial graph is connected with |E| \geq |V| - 1 edges; each valid deletion reduces the edge count by one while keeping the graph connected; and the process halts precisely when the subgraph is minimally connected, which for a connected graph with |V| vertices requires exactly |V| - 1 edges.[4][12]
Since the final subgraph is connected and contains exactly |V| - 1 edges, it satisfies the fundamental theorem of trees: a connected graph with |V| vertices and |V| - 1 edges is acyclic and thus a spanning tree. Deleting edges cannot introduce cycles, so the acyclicity follows directly from the edge count and connectivity in the connected component.[5][3] If the input graph is disconnected, the algorithm fails to produce a single spanning tree, but it assumes a connected input as standard.[12]
Minimality Proof
The minimality of the spanning tree produced by the reverse-delete algorithm follows from the cycle property of minimum spanning trees (MSTs): in any cycle of the graph, the maximum-weight edge cannot belong to any MST.[5]
To establish the cycle property, suppose for contradiction that some MST T includes the heaviest edge e = (u, v) on a cycle C. Removing e from T disconnects the graph into components S (containing u) and V \setminus S (containing v). The remaining edges of C form a path from u to v, which must cross the cut (S, V \setminus S) via at least one edge e' of weight less than that of e (since e is heaviest on C). Adding e' to T \setminus \{e\} yields a new spanning tree T' with strictly lower total weight than T, contradicting the minimality of T. Thus, no MST contains the heaviest edge of any cycle, and for any deleted heavy edge e, the lighter crossing edge e' in its cycle serves as a replacement across the relevant cut, ensuring optimality is preserved.[5][3]
In the reverse-delete algorithm, edges are processed in decreasing weight order, starting from the full graph. When considering an edge e, all heavier edges have already been either deleted (if they formed cycles with even heavier edges) or retained (if necessary for connectivity). If deleting e disconnects the current subgraph, it is kept; otherwise, the endpoints of e remain connected via a path of retained edges, all lighter than e. This path plus e forms a cycle where e is the heaviest edge. By the cycle property, e cannot belong to any MST, so deleting it is safe and does not preclude achieving minimum weight. Since the algorithm only deletes such non-MST edges and retains a spanning tree (as proven separately), the final output T contains no superfluous heavy edges and has minimal total weight among all spanning trees.[3][2]
An equivalent proof proceeds by contradiction. Suppose T is the output spanning tree but w(T) > w(T') for some MST T'. The symmetric difference T \Delta T' forms a collection of disjoint cycles, as both T and T' are acyclic and spanning. Across these cycles, the total weight difference implies at least one cycle where an edge e \in T has weight exceeding some edge f \in T' on the same cycle. Consider the heaviest such e \in T over all cycles; the path in T' replacing e consists of lighter edges. When the algorithm processed e (before lighter edges), this lighter path already existed in the current subgraph (as heavier edges were handled first), forming a cycle with e as heaviest, so e would have been deleted—contradicting e \in T. Thus, no lighter T' exists, confirming T is minimal.[4]
The reverse-delete algorithm yields the same MST as Kruskal's algorithm when edge weights are distinct, as both implement the greedy choice on the bases of the graphic matroid—selecting edges that avoid cycles while minimizing (or equivalently, not maximizing unnecessary) weight. This equivalence stems from the matroid exchange properties, ensuring the optimal basis is uniquely determined by sorted greedy selection in either direction for this structure.[13]