Kruskal’s algorithm to find an MST starts with an empty MST, then builds an MST

Question

Kruskal’s algorithm to find an MST starts with an empty MST, then builds an MST by continually adding the lightest edge possible to the MST it is building (without creating a cycle), until it has created a spanning tree. Consider an algorithm that finds an MST the opposite way. Start with an “MST” that consists of all the edges in the graph, and create the MST by continually deleted the heaviest edge in the “MST” (that doesn’t disconnect the graph) until it has gotten down to a spanning tree. Does this algorithm generate an MST? Explain

Explanation / Answer

Yes, this algorithm generates MST.

This algorithm is known as Reverse-Delete Algorithm.

Steps of Reverse-Delete Algorithm:

1) Start with original graph

2) Check the edges in decreasing order of wights.

3) Delete an edge if it does not disconnects the graph

It works in opposite way of Kruskal's algorithm. Basically kruskal's algorithm includes lesser weighted edges, whereas reverse-delete algorithm deletes heavier edges. Hence both algorithms find MST.

Related Questions

Navigate

• Browse (All)
• Browse K
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.