CODEWITHSUNDEEP
algorithmgraphgraph-algorithmdepth-first-search
Yosefki
Yosefki

Reputation: 393

Algorithm finding an MST using DFS

I have the following algorithm: For a given (finite undirected simple) graph G=(V,E) with positive weight function on the edges:

  1. Run DFS (depth-first-search) till you find an edge going backwards or DFS stopped. If stopped, return G.
  2. On the circle that is constructed by the backwards going edge find the heaviest edge and remove it from G.
  3. Return to 1.

Now I need to understand what this algorithm is doing. I have already proven that the algorithm gives me a spanning tree of G and I believe it's a minimum spanning tree but I fail to prove that. Please help me to prove that.

Upvotes: 0

Views: 2673

Answers (2)

Per
Per

Reputation: 2624

Prove that, when e is the heaviest edge in a cycle of G, the cost of the MST of G - e is no greater than the cost of the MST of G. (Let T be an MST for G and use T and the assumption about e to construct a spanning tree T' of G - e with cost(T') ≤ cost(T).) Conclude by induction on |E| that the algorithm produces an MST.

Upvotes: 1

biziclop
biziclop

Reputation: 49744

It looks like you're performing a variation of the reverse-delete algorithm but you still have to prove that your algorithm is equivalent with removing all the highest weighted edges that don't disconnect the graph.

Upvotes: 1

Related Questions