Second min cost spanning tree

Question

I'm writing an algorithm for finding the second min cost spanning tree. my idea was as follows:

1. Use kruskals to find lowest MST.
2. Delete the lowest cost edge of the MST.
3. Run kruskals again on the entire graph.
4. return the new MST.

My question is: Will this work? Is there a better way perhaps to do this?

Answer 1

You can do this -- try removing the edges of the MST, one at a time from the graph, and run the MST, taking the min from it. So this is similar to yours, except for iterative:

1. Use Kruskals to find MST.
2. For each edge in MST:
   1. Remove edge from graph
   2. Calculate MST' on MST
   3. Keep track of smallest MST
   4. Add edge back to graph
3. Return the smallest MST.