The Reverse-Delete algorithm is a graph algorithm used to find the minimum spanning tree (MST) of a connected and undirected graph. It is based on the concept of deleting edges and checking connectivity, which is a complement to the more commonly known Prim's and Kruskal's algorithms for finding MSTs. ### How the Reverse-Delete Algorithm Works: 1. **Initialization**: Start with the original graph, consisting of vertices and edges.
Articles by others on the same topic
Process edges in decreasing weight and delete an edge whenever the remaining graph stays connected. Previously retained heavier edges are bridges in a graph and remain so under deletion. Thus a deletable edge is heaviest on a current graph cycle, and the minimum spanning tree cycle property excludes it from every minimum spanning tree. At termination the surviving connected graph has no graph cycle, so it is a minimum spanning tree.