## Second Minimum spanning tree

Given an weighted undirected graph $G = (V, E)$, and $w : E \mapsto R^+$.

• Let T be MST i,e minimum spanning tree of graph G.
• Second MST is a Tree T' different from T, and its weight is less than weights of all other spanning trees of G except T.

Find the Second MST of an input graph in $O(|E|\log{|E|})$ time.

NOTE: There is also an O(|E|) solution to this which is quite complicated.

0

0

0

0

0

0

0

0

0

0