Algorithm to find the second best minimum spanning tree from a weighted graph

0
votes

I'm trying to find the second best minimum spanning three from a weighted unoriented graph. I know how to compute the MST using Kruskal algorithm, and I was thinking to find the second best minimum algorithm this way:

Steps:

  1. Sort all the graph edges.

  2. Compute the MST using Kruskal

  3. Get the minimum weight edge from the graph that is not in the first MST and add it to the MST (now the MST has a cycle)

  4. Remove the maximum weight edge in the new formed cycle

And this should be the second best MST right ?

By the way I know is a topic there pointing out an algorithm that iterates between each of the MST edges and runs Kruskal on the graph without the edge selected, I'm just asking if mine works.

2
algorithmgraphcomputer-science
Say your MST=(a,b),(b,c),(c,d),(d,e) with weights w(a,b)=w(b,c)=1 and w(c,d)=w(d,e)=4. Suppose edges (a,c) and (c,e) also exist with weights w(a,c)=4 and w(c,e)=5. Your algorithm will add (a,c) and remove one of the edges with weight 1, but the correct way would be to add (c,e) and remove one of the edges with weight 4. – Tony Tuttle
Yea you are right,thank you ! – Eduard Valentin

2 Answers

1
votes

It does not work.

After step 3, the newly added edge might become part of a cycle containing only edges with very low costs, so after steps 3 and 4, the overall cost of the MST can increase significantly.

On the other hand, the graph might contain another edge with similar cost to the one selected at step 3, which, when added in the MST, would be part of another cycle, say, containing edges with relatively high costs. Selecting this edge for step 3, and then applying step 4 would lead to another spanning tree, better than the one generated by the proposed algorithm.

1
votes

No, your algorithm doesn't work.

  1        3
 /--\  2  /--\
.    .---.    .
 \--/     \--/
  4        5

The MST is 1,2,3 => 6.

The second best is 1,2,5 => 8.

Your algorithm will return 2,3,4 => 9.

(I'm assuming your step 4 is to return the maximum weight edge that's not the one you just added)

The key here is that the difference between 1 and 4 (3) is greater than the difference between 3 and 5 (2), so replacing 3 with 5 results in a lower overall cost than replacing 1 with 4.