Second min cost spanning tree.

Question

Hello. 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

Consider this case:

------100----
|           |
A--1--B--3--C
      |     |
      |     3
      |     |
      2-----D

The MST consists of A-B-D-C (cost 6). The second min cost is A-B-C-D (cost 7). If you delete the lowest cost edge, you will get A-C-B-D (cost 105) instead.

So your idea will not work. I have no better idea though...

Answer 2

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.

Answer 3

You can do it in O(V²). First compute the MST using Prim's algorithm (can be done in O(V²)).

Compute max[u, v] = the cost of the maximum cost edge on the (unique) path from u to v in the MST. Can be done in O(V²).

Find an edge (u, v) that's NOT part of the MST that minimizes abs(max[u, v] - weight(u, v)). Can be done in O(E) == O(V²).

Return MST' = MST - {the edge that has max[u, v] weight} + {(u, v)}, which will give you the second best MST.

Here's a link to pseudocode and more detailed explanations.