Second-Best MST, in depth: the one-swap theorem, strict versus non-strict, path-maximum queries with binary lifting and a brute-force test

Two definitions of second best

Let G be a connected, undirected, weighted graph with n vertices and m edges. A spanning tree uses n - 1 edges to connect all vertices; its weight is the sum of its edge weights. Let T be a minimum spanning tree with weight W. There are two common definitions of second best, and mixing them up is the most frequent bug.

• Non-strict: the minimum weight over spanning trees whose edge set differs from T. If weights tie, the answer can equal W, because another tree of the same weight exists.
• Strict: the minimum weight over spanning trees whose weight is strictly greater than W. It may not exist, for example when G itself is a tree, or when every spanning tree has weight W.

With distinct weights the MST is unique and the definitions coincide. Contests usually want strict; network design usually wants non-strict, since an equal-cost alternative is worth knowing about.

Why one swap is enough

Two facts drive everything. The cycle property: adding any non-tree edge e = (u, v) to T creates exactly one cycle, made of e plus the tree path from u to v, and because T is minimum, w(e) is at least as large as every tree edge on that path. The exchange property: removing any edge f on that cycle gives another spanning tree, T + e - f, of weight W + w(e) - w(f).

The swap theorem says some second-best tree is of the form T + e - f. A sketch of the proof: take a second-best tree S that shares as many edges with T as possible. If S differs from T in more than one edge, pick an edge e in S but not in T. Removing e from S splits it into two components, and the path in T between e's endpoints crosses between them through some edge f of T that is not in S. Because T is minimum, w(f) is at most w(e), so S - e + f is a spanning tree no heavier than S that shares one more edge with T. It still differs from T, because S differed in at least two edges, so it is also second-best, contradicting the choice of S. The strict variant has the same one-swap property, with a more careful exchange argument; the brute-force test later checks it empirically.

For a non-tree edge e, the best partner f is the heaviest edge on the tree path between e's endpoints, because that minimizes w(e) - w(f). For the strict variant, if the heaviest edge has weight exactly w(e), the swap gives weight W, which is not allowed, so use the heaviest path edge whose weight is strictly less than w(e). That is why strict solutions carry the top two distinct weights on each path, not just the maximum.

Worked example

Take six vertices A to F and nine edges: A-B 1, B-C 2, C-D 4, A-C 5, D-E 6, B-D 7, E-F 8, D-F 9 and C-E 10. Kruskal's algorithm sorts the edges and takes each one that joins two components. It takes A-B, B-C and C-D; skips A-C because A and C are already connected; takes D-E; skips B-D; takes E-F; and skips D-F and C-E. The MST is the path A-B-C-D-E-F with weight 1 + 2 + 4 + 6 + 8 = 21.

Now evaluate each non-tree edge. A-C closes the cycle A-B-C, whose heaviest tree edge is B-C at 2, so the swap costs 5 - 2 = 3. B-D closes B-C-D with maximum 4: cost 3. C-E closes C-D-E with maximum 6: cost 4. D-F closes D-E-F with maximum 8: cost 1. The best swap is add D-F, remove E-F, and the second-best tree weighs 22.

Change one weight to see the strict trap. Set D-F to 8, equal to E-F. The heaviest edge on D-E-F is now exactly 8, so the swap costs 0: under the non-strict definition the answer is 21, a different tree of the same weight. Under the strict definition that swap is illegal, so use the second-largest distinct weight on the path, D-E at 6, for a cost of 2 and a tree of weight 23. The other swaps cost 3, 3 and 4, so the strict answer is 23. Tracking only the maximum prints 21 or 24; both are wrong.

The naive algorithm and a better framing

The obvious algorithm is to build the MST, then for each of its n - 1 edges, ban that edge and rerun Kruskal on the rest, taking the minimum. It is correct for the non-strict version and costs O(n m) after one sort: fine at n = 1,000, hopeless at n = 100,000.

The better framing inverts the loop: for each non-tree edge, find the heaviest tree edge on the path between its endpoints. That is a path-maximum query on a tree.

Dense graphs: all-pairs path maximum in O(n squared)

For dense graphs, precompute every pair. Run a DFS or BFS from each vertex s over the tree and record, for every vertex x, the heaviest edge on the path from s to x: when the search moves from x to child y across an edge of weight w, set best[s][y] to the larger of best[s][x] and w. Each search is O(n), so the table costs O(n squared) time and memory, and each non-tree edge is then answered in O(1). With Prim's O(n squared) algorithm on an adjacency matrix, the whole problem is O(n squared). For the strict version store the top two distinct weights per pair. At n = 5,000 the table holds 25 million entries; at 8 bytes each that is 200 MB, which is the practical ceiling.

Sparse graphs: binary lifting with top-two maxima

For sparse graphs, root the MST and use binary lifting. For each vertex v and each k, store up[k][v], the 2 to the k-th ancestor of v, and the largest and second-largest distinct edge weights on the path from v up to that ancestor. Level 0 comes from the parent edge; level k merges two level k - 1 jumps. A path query lifts the deeper endpoint to the same depth, then lifts both endpoints together until their parents meet, merging the top-two summaries of every jump. Preprocessing is O(n log n), each query O(log n), so the total with Kruskal is O(m log m + m log n).

NEG = float("-inf")

def top2(*vals):
    """Largest and second-largest DISTINCT values (NEG if absent)."""
    m1 = max(vals)
    m2 = max((v for v in vals if v < m1), default=NEG)
    return m1, m2

def second_best_mst(n, edges, strict=True):
    """edges: list of (w, u, v) with 0 <= u, v < n. Returns (mst_weight, second_or_None)."""
    parent = list(range(n))
    def find(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]
            x = parent[x]
        return x

    in_tree = [False] * len(edges)
    adj = [[] for _ in range(n)]
    total = used = 0
    for i in sorted(range(len(edges)), key=lambda i: edges[i][0]):
        w, u, v = edges[i]
        ru, rv = find(u), find(v)
        if ru != rv:
            parent[ru] = rv
            in_tree[i] = True
            total += w
            used += 1
            adj[u].append((v, w))
            adj[v].append((u, w))
    if used != n - 1:
        raise ValueError("graph is disconnected: no spanning tree")

    LOG = max(1, (n - 1).bit_length())
    up = [[0] * n for _ in range(LOG)]
    m1 = [[NEG] * n for _ in range(LOG)]
    m2 = [[NEG] * n for _ in range(LOG)]
    depth, seen, stack = [0] * n, [False] * n, [0]
    seen[0] = True
    while stack:                                  # iterative DFS: no recursion limit
        x = stack.pop()
        for y, w in adj[x]:
            if not seen[y]:
                seen[y] = True
                depth[y] = depth[x] + 1
                up[0][y], m1[0][y] = x, w
                stack.append(y)
    for k in range(1, LOG):
        for v in range(n):
            mid = up[k - 1][v]
            up[k][v] = up[k - 1][mid]
            m1[k][v], m2[k][v] = top2(m1[k - 1][v], m2[k - 1][v], m1[k - 1][mid], m2[k - 1][mid])

    def path_top2(u, v):
        best = (NEG, NEG)
        if depth[u] < depth[v]:
            u, v = v, u
        diff, k = depth[u] - depth[v], 0
        while diff:
            if diff & 1:
                best = top2(*best, m1[k][u], m2[k][u])
                u = up[k][u]
            diff >>= 1
            k += 1
        if u == v:
            return best
        for k in range(LOG - 1, -1, -1):
            if up[k][u] != up[k][v]:
                best = top2(*best, m1[k][u], m2[k][u], m1[k][v], m2[k][v])
                u, v = up[k][u], up[k][v]
        return top2(*best, m1[0][u], m1[0][v])

    answer = None
    for i, (w, u, v) in enumerate(edges):
        if in_tree[i] or u == v:                  # tree edges and self-loops never help
            continue
        a, b = path_top2(u, v)                    # a <= w by the cycle property
        if a < w:
            cand = total + w - a
        elif not strict:
            cand = total                          # equal-weight alternative tree
        elif b != NEG:
            cand = total + w - b
        else:
            continue
        if answer is None or cand < answer:
            answer = cand
    return total, answer

On the worked example, second_best_mst(6, edges) returns (21, 22); with D-F set to 8 it returns (21, 23) in strict mode and (21, 21) in non-strict mode.

Edge cases and alternatives

A disconnected graph has no spanning tree; raise. A graph with exactly n - 1 edges is a tree and has no second-best; return None. Parallel edges are fine: a parallel non-tree edge's path is the single tree edge between the same endpoints. Self-loops never belong to a spanning tree and must be skipped, or the path query returns minus infinity and the swap looks free. In C++ or Java, sum weights in 64-bit integers; a tree of 200,000 edges with weights near a billion overflows 32 bits. Floating-point weights make the strict comparison fragile; scale to integers where you can.

Alternatives: a Kruskal reconstruction tree answers non-strict path maxima as the weight at the lowest common ancestor, and heavy-light decomposition with a segment tree supports weight updates.

Testing against brute force

Compare against brute force on thousands of small random graphs, with a narrow weight range to force ties.

import itertools, random

def brute(n, edges, strict=True):
    weights = []
    for combo in itertools.combinations(range(len(edges)), n - 1):
        parent = list(range(n))
        def find(x):
            while parent[x] != x:
                x = parent[x]
            return x
        ok = True
        for i in combo:
            _, u, v = edges[i]
            ru, rv = find(u), find(v)
            if ru == rv:
                ok = False
                break
            parent[ru] = rv
        if ok:
            weights.append(sum(edges[i][0] for i in combo))
    weights.sort()
    if strict:
        bigger = [w for w in weights if w > weights[0]]
        return weights[0], (bigger[0] if bigger else None)
    return weights[0], (weights[1] if len(weights) > 1 else None)

for trial in range(3000):
    n = random.randint(2, 6)
    edges = [(random.randint(1, 4), i, random.randrange(i)) for i in range(1, n)]   # spanning backbone
    edges += [(random.randint(1, 4), random.randrange(n), random.randrange(n)) for _ in range(random.randint(0, 5))]
    edges = [e for e in edges if e[1] != e[2]]
    for strict in (True, False):
        assert second_best_mst(n, edges, strict) == brute(n, edges, strict), (n, edges, strict)

Run both modes; the strict branch is where bugs hide.

Where it is used

In network design the gap between the best and second-best tree is a sensitivity measure: zero means an equal-cost alternative exists. A related operational question asks, for each tree edge, the cheapest replacement if that edge fails; the same path machinery answers it. Second-best is also the base case of k-best spanning tree enumeration, which partitions the solution space and finds the best swap inside each partition, with some edges forced in and some forbidden.

Failure modes

Most wrong answers trace back to one of these:

• Tracking only the maximum in strict mode. Equal weights make the best swap cost zero; without the second distinct maximum the code prints W or skips a valid swap.
• Top-two merging that keeps duplicates. Merging (8, 6) with (8, 5) must give (8, 6), not (8, 8).
• Forgetting the final step to the LCA. After the joint lift, the two parent edges of u and v are still unmerged.
• Recursive DFS in Python. Deep trees exceed the recursion limit; use an explicit stack.
• Assuming connectivity. Kruskal on a disconnected graph returns a forest, and the code reports a nonsense weight unless it checks the edge count.
• 32-bit sums. Large trees overflow silently in languages with fixed-width integers.

Trade-offs

What to do next

To make this stick:

1. Trace the six-vertex example by hand in both modes, including the D-F = 8 variant.
2. Implement the binary-lifting version and run the brute-force harness in both modes until it passes 3,000 trials.
3. Port it to C++ with 64-bit sums and time it on n = 200,000, m = 500,000.
4. Extend it to report, for every tree edge, the cheapest replacement edge if that edge fails.
5. Review Kruskal's algorithm and Prim's algorithm for the first step, union-find for the component checks, and lowest common ancestor for the lifting technique the path query uses.