<p>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.</p>

<p>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", <em>Algorithmica</em> 1997, <a href="http://dx.doi.org/10.1007/BF02526037">doi:10.1007/BF02526037</a>.</p>

CC BY-SA 3.0
2014-10-15T08:45:49.707Z
How do you know that this is the second-smallest tree, rather than the 50.th smallest tree?
Taemyr
CC BY-SA 3.0
2014-10-15T16:33:08.940Z
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, http://dx.doi.org/10.1007/BF01835983
David Eppstein
CC BY-SA 3.0
2014-10-15T02:51:46.737Z
2014-10-15T02:51:46.737Z
David Eppstein
<p>Could not add a comment due to lack of reputation.<br />
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
&quot;A combinatorial ranking problem&quot;, Burns and Haff.</p>
<p>Basically, in the article an algorithm is presented for finding an <span class="math-container">$n$</span>th-best spanning tree of an edge-weighted graph <span class="math-container">$G$</span> with time <span class="math-container">$O(n)$</span>.</p>
<p>And the link to read the paper for free is <a href="https://booksc.org/book/6732566/196389" rel="nofollow noreferrer">https://booksc.org/book/6732566/196389</a>.</p>

CC BY-SA 4.0
2014-10-20T16:27:24.150Z
2021-01-29T12:33:42.807Z
2021-01-29T12:33:42.807Z
Temak
<p>The classic Mininum Spanning Tree (MST) algorithms can be modified to find the Maximum Spanning Tree instead.</p>

<p>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.</p>

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

CC BY-SA 3.0
2014-10-16T13:00:15.677Z
The second cheapest path problem, called next-to-shortest path, is also interesting.
Bangye
CC BY-SA 3.0
2014-10-16T23:36:45.530Z
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.
Tsuyoshi Ito
CC BY-SA 3.0
2014-10-26T01:49:01.030Z
IIRC, this is an exercise in CLRS. Voting to close.
Kaveh
CC BY-SA 4.0
2019-02-11T17:47:19.790Z
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.
Remon Hasan
<graph-algorithms><tree>
How can I find the second cheapest spanning tree?
user3783608
# How can I find the second cheapest spanning tree?

(Asked by: username_0 on 2014-10-15)

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?

**Tags:** graph-algorithms, tree
> **Comments:**
> **username_1**: The second cheapest path problem, called next-to-shortest path, is also interesting.  
> **username_2**: 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.  
> **username_3**: IIRC, this is an exercise in CLRS. Voting to close.  
> **username_4**: 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.  

---

## 2 answers

### Answer by username_5 on 2014-10-15. Score: 21

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](http://dx.doi.org/10.1007/BF02526037).

> **Comments:**
> **username_6**: How do you know that this is the second-smallest tree, rather than the 50.th smallest tree?  
> **username_5**: 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, http://dx.doi.org/10.1007/BF01835983  

---

### Answer by username_7 on 2014-10-20. Score: 4

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)$.

And the link to read the paper for free is <https://booksc.org/book/6732566/196389>.


---

