Subscribe to the weekly news from TrueShelf

0

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.

Related Content