Reverse-Delete Algorithm

The reverse-delete algorithm is a graph theory algorithm used to obtain a minimum spanning tree, or for a disconnected graph a minimum spanning forest touching every vertex, from a connected, edge-weighted graph. It first appeared in a 1956 paper by Joseph Kruskal, though it should not be confused with Kruskal's algorithm from the same paper: Kruskal's algorithm is a greedy algorithm that starts with an empty graph and adds edges, while the reverse-delete algorithm starts with the original graph and deletes edges from it in decreasing order of weight whenever a deletion would not further disconnect the graph.