Sign in to watch this lesson
Advanced - Graphs · 4:02
Second-Best MST
The cheapest spanning tree that costs strictly more than the minimum differs from a minimum spanning tree by one swap: add a non-tree edge and remove an edge on the cycle it closes. Banning each tree edge and rerunning Kruskal finds it in O(VE); taking, for every non-tree edge, the heaviest tree edge on its path through the LCA finds it in O(E log V) with binary lifting, as long as we fall back to the strict second maximum when the maximum ties the new edge. The same path maximum gives the cheapest tree that must contain a given edge.
You will learn
- Explain why the second-best spanning tree differs from a minimum spanning tree by exactly one edge swap
- Find it in O(VE) by banning each tree edge and rerunning Kruskal on pre-sorted edges
- Find it in O(E log V) by taking each non-tree edge's tree-path maximum through the LCA, keeping the top two distinct weights per binary-lifting jump
- Answer 'cheapest spanning tree that must contain edge e' as MST + w(e) − maxOnPath(u, v)