# How can I find the second cheapest spanning tree?

The classic Mininum Spanning Tree (MST) algorithms can be modified to find the Maximum Spanning Tree instead.

Can an algorithm such as Kruskal's be modified to return a spanning tree that is strictly more costly than an MST, but is the second cheapest? For example, if you switch one of the edges in this spanning tree, you end up with an MST and vice versa.

My question, though, is simply: How can I find the second cheapest spanning tree, given a graph $G$ with an MST?

• The second cheapest path problem, called next-to-shortest path, is also interesting. Oct 16 '14 at 13:00
• The original title of this question was “Minimum to Maximum spanning trees?” That described the first paragraph of the post, which might be the original motivation for your question, but was not your question. When you post a question next time, please try to give it a title which describes your question. Oct 16 '14 at 23:36
• IIRC, this is an exercise in CLRS. Voting to close. Oct 26 '14 at 1:49
• Is it the process ? 1. Finding MST from a given graph. 2. removing the edge of maximum weight from the MST. 3. Then adding the edge in the MST from the given which weight is below the removing edge from the MST. Feb 11 '19 at 17:47

The second-smallest spanning tree differs from the minimum spanning tree by a single edge swap. That is, to get the second-smallest tree, you need to add one edge that's not already in the minimum spanning tree, and then remove the heaviest edge on the cycle that the added edge forms.

If you already have the minimum spanning tree, this can all be done in linear time. See e.g. V. King, "A simpler minimum spanning tree verification algorithm", Algorithmica 1997, doi:10.1007/BF02526037.

• How do you know that this is the second-smallest tree, rather than the 50.th smallest tree? Oct 15 '14 at 8:45
• It's easy to prove yourself. But if you'd rather just look it up there's a proof in "A combinatorial ranking problem", Burns and Haff, Aeq. Math. 1976, dx.doi.org/10.1007/BF01835983 Oct 15 '14 at 16:33

Could not add a comment due to lack of reputation.
As commented by David Eppstein you can find the proof of the fact that the second-smallest spanning tree differs from the minimum spanning tree by a single edge swap in the article "A combinatorial ranking problem", Burns and Haff.

Basically, in the article an algorithm is presented for finding an $$n$$th-best spanning tree of an edge-weighted graph $$G$$ with time $$O(n)$$.