Pitsarakos's blog

Fastest way to find the second mst (minimum spanning tree)
By Pitsarakos, 11 years ago, In English

Can anybody explain me how to find the second minimum spanning tree in the fastest way, I heard about disjoint sets I studied them but I still can't find the way to do it...

  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (9)
| Write comment?
»
11 years ago, # |
← Rev. 3   Vote: I like it +7 Vote: I do not like it

I guess follow solution can be correct.
build MST. Then build a tree from edges of MST. Now if you try to add any other edge into a tree it makes a cycle in the new graph. find the edge with the maximal cost on the cycle and remove it from graph. Now graph is a tree again. Try all edges and choose the minimal possible tree (make shure it is not another MST). you can find maximal edge on the cycle in LogN using LCA(LeastCommonAncestor) and some other data structures.

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    O(M logN) for Kruskal and O(M logN) again for M queries with LCA. It will work.

    → Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    thank you, I also came up with the idea of disjoint-sets to check if there is a cycle. Anw thanks everybody for helping.

    → Reply
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

First off, build the minimum spanning tree, then, for each edge of the minimum spanning tree, build a new one discarding such edge. The minimum one will be the second minimum spanning tree. Using Kruskal algorithm and a O(n * log(n)) sorting algorithm for the edges, this strategy lead to a O(N^2 * log(N)) overall complexity.

→ Reply
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

You can make use of the LCA algorithm and the observation that the second mst will differ from the first by only one edge to make the algorithm described by aajjbb run in O( ElogV ) time

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Could you please provide some code for this O(ElogV) algorithm ?

    → Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

We can achieve this in O(E * log(N)) time using heavy-light decomposition. E = Number of Edges You can find more about heavy light decomposition here : Heavy Light Decomposition

Basically for every edge which you consider to add into the MST(Minimum Spanning Tree) to make it second minimum spanning tree, let us say it connects two vertices A and B.

Now after adding this new edge we need to remove one edge which is the smallest among the edges that lie in the path between A and B in the original MST. This can be achieved using Heavy Light Decomposition on the MST in Log(N) time for one edge. So it takes O(E * Log(N)) total time.

Source: https://www.quora.com/How-do-I-get-a-second-minimum-spanning-tree (Answer by adurysk)

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Your general idea is correct, though you need to remove the largest edge on the path from A to B, not the smallest one. And also, you can achieve that without heavy-light decomposition. Two LCA-like data structures will solve it (one for ancestors, one for maximum edges).

    → Reply