Overview
Reverse-delete sorts edges from highest to lowest weight and removes an edge whenever the graph remains connected without it.
CoreSource checked
Reverse-Delete Algorithm
Builds a minimum spanning tree by deleting expensive edges that are not needed for connectivity.
Quick Facts
Compact metadata for implementation and discovery.
- Category
- Graph Traversal
- Difficulty
- Intermediate
- Family
- Minimum Spanning Tree
- Tier
- Core
- Status
- Verified
- Review
- Source Checked
- Sources
- 2
- Formulas
- 0
- Relationships
- 4
- Code example
- Ready
- Visualization
- Ready
Core Concepts
minimum spanning tree constructionminimum spanning treegraph traversal
Quick facts
Complexity
Runtime and memory behavior at a glance.
Best
O(V + E)
Average
O((V + E) log V)
Worst
O(V^2 + E)
Space
O(V + E)
When to Use
- Use as a conceptually simple MST method that mirrors Kruskal's greedy choice in reverse.
- Use for teaching cut/cycle properties or for small graphs.
When Not to Use
- Avoid when repeated connectivity tests would be too expensive.
- Avoid on disconnected graphs unless computing a minimum spanning forest is intended.
What It Does
- Computes minimum spanning tree within Minimum Spanning Tree workloads (O((V + E) log V) time, O(V + E) space).
- Works by Builds a minimum spanning tree by deleting expensive edges that are not needed for connectivity.
- Maintains key invariants across minimum spanning tree construction, minimum spanning tree, graph traversal.
Use Cases
- Production and research workloads requiring minimum spanning tree via Builds a minimum spanning tree by deleting expensive edges that are not needed for connectivity.
- Minimum Spanning Tree pipelines where O((V + E) log V) time and O(V + E) space fit system constraints.
- Engineering comparisons against Boruvka's Algorithm and Minimum Spanning Tree when tuning minimum spanning tree.
Inputs
- Minimum Spanning Tree input instance for minimum spanning tree
- Configuration parameters controlling minimum spanning tree construction
Outputs
- Computed minimum spanning tree solution produced by Reverse-Delete Algorithm
- Diagnostic state over minimum spanning tree construction and minimum spanning tree
Pseudocode
- 1.Sort edges by decreasing weight
- 2.Start with all graph edges present
- 3.For each edge e in sorted order
- 4.Remove e temporarily
- 5.If the graph is disconnected, restore e
- 6.Return the remaining edges
Canonical Example
- Input
- triangle edges AB=1, BC=2, AC=3
- Output
- remove AC and keep AB, BC
- Explanation
- The heaviest edge AC is redundant because A still reaches C through B.
Implementation Notes
- Sort edges in descending weight order.
- For each edge, temporarily remove it and test whether its endpoints remain connected.
- Keep the edge if removing it disconnects the current graph.
Common Pitfalls
- Removing an edge without checking connectivity can disconnect the graph.
- Equal-weight edges may produce different valid MSTs.
- The input must be undirected for the standard MST interpretation.
Interactive Mechanism Walkthrough
Graph Frontier & Edge RelaxationShow removing expensive edges when their removal does not disconnect the graph on a small minimum spanning tree construction example.
Step 1 of 6: Sort edges by decreasing weight
graph-traversal-mechanismNotes
Reverse-delete is usually less practical than Kruskal with union-find, but it exposes the same MST greedy structure.
Sources (2)
What each reference supports for this entry.
Introduction to Algorithms (CLRS)
BookTextbook support for Reverse-Delete Algorithm's algorithm family, complexity framing, and standard implementation concepts.
Open sourceThe Algorithm Design Manual
BookAlgorithm catalog support for Reverse-Delete Algorithm in the graph, flow, matching, and combinatorial optimization benchmark area.
Open sourceExplore Next
Good next jumps from the relationship graph, ranked for useful discovery.
UsesBoruvka's Algorithm
Graph Traversal · Core
Reverse-Delete Algorithm uses Boruvka's Algorithm as a subroutine, representation, or supporting idea while removing expensive edges when their removal does not disconnect the graph.
Compare with thisRelationships
View full relationship pageReverse-Delete Algorithm uses Boruvka's Algorithm as a subroutine, representation, or supporting idea while removing expensive edges when their removal does not disconnect the graph.
Reverse-Delete Algorithm uses Minimum Spanning Tree as a subroutine, representation, or supporting idea while removing expensive edges when their removal does not disconnect the graph.
Reverse-Delete Algorithm uses Kruskal's Algorithm as a subroutine, representation, or supporting idea while removing expensive edges when their removal does not disconnect the graph.
Tags
GraphTraversal