11.13 Second-Best Spanning Tree

A minimum spanning tree gives the cheapest way to connect all vertices.

algorithmsgraphsspanning-trees

11.13 Second-Best Spanning Tree

Problem

A minimum spanning tree gives the cheapest way to connect all vertices. In practice, the cheapest tree may not be the only tree worth knowing.

A cable route may become unavailable. A road segment may be blocked by regulation. A network design may need a backup plan. A contest problem may ask for the next larger spanning tree cost. In each case, you need the second-best spanning tree.

The second-best spanning tree is the spanning tree with the smallest total weight strictly greater than the MST, unless the problem allows ties. Because different sources define “second-best” differently, establish the contract first:

Strict second-best:
    minimum spanning tree cost greater than MST cost

Non-strict second-best:
    minimum spanning tree different from the chosen MST,
    possibly with the same total cost

This section uses the strict version unless stated otherwise.

Solution

The standard method starts with one MST.

Then, for every edge not in the MST:

  1. Add that edge to the MST.
  2. This creates exactly one cycle.
  3. Remove the maximum-weight edge on the path between the two endpoints.
  4. The result is another spanning tree.
  5. Track the smallest cost greater than the MST cost.

This works because every spanning tree that differs from the MST by one edge can be viewed as an exchange.

Example

Graph edges:

Edge Weight
A-B 1
B-C 2
C-D 3
A-D 4
A-C 5

One MST is:

A-B
B-C
C-D

MST cost:

1 + 2 + 3 = 6

Now consider non-tree edge:

A-D = 4

In the MST, the path from A to D is:

A -> B -> C -> D

Path edge weights:

1, 2, 3

Maximum edge on that path:

3

Add A-D and remove C-D.

New cost:

6 + 4 - 3 = 7

Now consider non-tree edge:

A-C = 5

Path in MST:

A -> B -> C

Maximum path edge:

2

New cost:

6 + 5 - 2 = 9

The strict second-best spanning tree has cost:

7

Why One Edge Exchange Is Enough

Let T be an MST.

Take any other spanning tree T'.

There is at least one edge:

e ∈ T' but e ∉ T

Add e to T. This creates a cycle. That cycle contains at least one edge:

f ∈ T but f ∉ T'

Replacing f with e gives another spanning tree.

For finding the best immediate alternative to an MST, we can examine all such single-edge exchanges. The minimum valid exchange gives the second-best candidate.

Cost Formula

For a non-tree edge:

e = (u, v, w)

adding it to the MST creates a cycle along the existing path from u to v.

Let:

maxEdge(u, v)

be the maximum edge weight on that path.

The candidate cost is:

mstCost + w - maxEdge(u, v)

This formula is the heart of the algorithm.

Naive Algorithm

Build an MST with Kruskal or Prim. Then process every non-tree edge.

For each non-tree edge:

  1. Run DFS or BFS on the MST to find the path between its endpoints.
  2. Find the maximum-weight edge on that path.
  3. Compute the candidate cost.
  4. Keep the smallest candidate greater than mstCost.

Pseudocode

SecondBestMST(G):

    T, mstCost = Kruskal(G)

    answer = infinity

    for each edge(u, v, w) not in T:

        pathMax = maximum edge weight
                  on path u -> v in T

        candidate = mstCost + w - pathMax

        if candidate > mstCost:
            answer = min(answer, candidate)

    return answer

This is easy to implement and good enough for small graphs.

Complexity of the Naive Version

Building the MST costs:

O(E log E)

For each non-tree edge, scanning the tree may cost:

O(V)

Total:

O(EV)

This can be too slow when both E and V are large.

Faster Algorithm with Binary Lifting

The expensive operation is:

maximum edge on tree path u -> v

This is a classic tree query.

Preprocess the MST using binary lifting. Store, for each vertex and each jump length:

up[k][v]      = the 2^k-th ancestor of v
maxUp[k][v]   = maximum edge weight on the path from v to up[k][v]

Then a maximum-edge path query can be answered in:

O(log V)

After preprocessing, each non-tree edge gives a candidate in logarithmic time.

Binary Lifting Query

To compute maxEdge(u, v):

  1. Lift the deeper vertex until both vertices have the same depth.
  2. Lift both vertices upward together until their ancestors meet.
  3. Track the maximum edge weight seen during all jumps.
  4. The meeting point is the lowest common ancestor.

This gives the maximum edge on the path.

Faster Pseudocode

SecondBestMST(G):

    T, mstCost = Kruskal(G)

    build adjacency list of T

    preprocess depth, up, maxUp using DFS

    answer = infinity

    for each edge(u, v, w) not in T:

        pathMax = queryMaxEdge(u, v)

        candidate = mstCost + w - pathMax

        if candidate > mstCost:
            answer = min(answer, candidate)

    return answer

Complexity

Step Complexity
Build MST O(E log E)
Preprocess tree O(V log V)
Process non-tree edges O(E log V)
Total O(E log E + V log V + E log V)

Since usually:

E ≥ V - 1

this is commonly written as:

O(E log V)

after sorting assumptions are normalized.

Handling Equal Weights

Equal weights require care.

Suppose:

mstCost = 10

and an exchange produces:

candidate = 10

For strict second-best, ignore it.

For non-strict second-best, accept it if the resulting tree differs from the chosen MST.

This distinction matters in graphs with multiple MSTs.

Strict Second-Best with Equal Path Max

The basic formula removes the maximum edge on the cycle. If w equals the maximum edge weight, the candidate cost equals the MST cost.

For the strict variant, that candidate is not enough. You may need to remove the largest edge on the path that is strictly smaller than w.

This is why some implementations store the two largest distinct edge weights on each binary-lifting jump:

largest edge
second-largest distinct edge

Then, for a non-tree edge with weight w:

if largest < w:
    remove largest
else:
    remove second-largest distinct edge

This avoids accidentally returning another MST when the task asks for the strictly larger answer.

Example with Equal Weights

MST cost:

10

Non-tree edge weight:

5

Maximum edge on path:

5

Candidate:

10 + 5 - 5 = 10

This is another MST, not a strict second-best tree.

If the second-largest distinct edge on the path is:

3

then a strict candidate is:

10 + 5 - 3 = 12

provided that removing that edge still corresponds to the cycle exchange.

Implementation Details

Track whether each edge belongs to the MST.

In Kruskal, assign every edge a unique ID before sorting:

edge = (id, u, v, weight)

When an edge is accepted, mark:

inMST[id] = true

Later, iterate over all edges where:

inMST[id] == false

This avoids ambiguity when multiple edges connect the same vertices with the same weight.

Disconnected Graphs

If the original graph is disconnected, there is no spanning tree.

In that case, the correct output is usually one of:

no spanning tree
impossible
null

depending on the API or problem statement.

Do not return a numeric second-best value unless a spanning tree exists.

Common Mistakes

Removing the Non-Tree Edge

After adding a non-tree edge, remove an edge from the cycle in the original MST path, not the edge you just added.

Searching the Original Graph

The path query must run on the MST, not the original graph.

Ignoring Edge IDs

Parallel edges can have the same endpoints and weight. Use unique edge IDs.

Mishandling Equal Weights

Decide whether second-best means strictly larger cost or merely a different tree.

Forgetting the No-Answer Case

Some graphs have only one spanning tree. Then no alternative spanning tree exists.

Recipe

Use this pattern for second-best spanning tree problems:

  1. Build an MST with Kruskal or Prim.
  2. Mark all MST edges by unique ID.
  3. Build a tree adjacency list from the MST.
  4. Preprocess maximum edge queries on tree paths.
  5. For every non-tree edge, compute mstCost + w - maxEdge(u, v).
  6. Keep the smallest candidate allowed by the problem contract.
  7. Treat equal weights and disconnected graphs explicitly.

The second-best spanning tree is an exchange problem over an MST. The MST gives the base solution; every non-tree edge proposes one controlled modification. The hard part is not the idea, but answering path-maximum queries quickly and defining “second-best” precisely.