Question

When Kruskal invented the algorithm that finds minimumspanning trees by adding edges in order of increasing weightas long as they do not form a simple circuit, he also inventedanother algorithm sometimes called the reverse-delete algorithm. This algorithm proceeds by successively deletingedges of maximum weight from a connected graph as long asdoing so does not disconnect the graph.

Express the reverse-delete algorithm in pseudocode.

Short answer

Procedure reverse-delete(\({\bf{G}}\): connected simple graph with\({\bf{n}}\)vertices)

\({\bf{T: = G}}\)

while\({\bf{T}}\)has more than\({\bf{n - 1}}\)edges.

\({\bf{e: = }}\)edge with largest weight in a simple circuit of\({\bf{T}}\)

\({\bf{T: = T - }}\left\{ {\bf{e}} \right\}\)

return\({\bf{T}}\)

Step-by-step solution

Definition

A graph is connected if there exists a path between every pair of vertices.

Reverse-delete algorithm:

Start from the given graph \({\bf{G}}\) with \({\bf{n}}\) vertices. Repeatedly remove the edge with the largest weight from the graph \({\bf{G}}\) as long as it doesn't disconnect \({\bf{G}}\).The algorithm stops when the resulting graph contains only \({\bf{n - 1}}\) edges (as a spanning tree of \({\bf{G}}\) containing \({\bf{n}}\) vertices has\({\bf{n - 1}}\) edges).

Using the reverse delete algorithm

We call the algorithm "reverse-delete" and the input is a connected simple graph \({\bf{G}}\) procedure

reverse-delete(\({\bf{G}}\) : connected simple graph with \({\bf{n}}\) vertices) We start from the given graph \({\bf{G T: = G}}\) We repeatedly remove the edge with the largest weight as long as it doesn't disconnect the graph. We end the algorithm when thegraph has only \({\bf{n - 1}}\) edges remaining. while \({\bf{T}}\) has more than \({\bf{n - 1}}\) edges. \({\bf{e: = }}\) edge with largest weight in a simplecircuit of \({\bf{T}}\;\;\;{\bf{T: = T - \{ e\} }}\) Finally, we return \({\bf{T}}\) which should contain the minimum spanning tree. return \({\bf{T}}\).