題目

考慮一張無向的加權圖

G = V, E, w (s, t)

，求

G

的生成樹中，權重非嚴格第二大的生成樹。

演算法

先找出 $G$ 的最小生成樹 $G_{M} = V_{M}, E_{M}, w_{M} (s, t)$
設 $S = \emptyset$
對於所有的邊 $e = s, t \in E - E_{M}$
1. 找到 $G_{M}$ 中，點 $s$ 到點 $t$ 的路徑上，邊長最長的邊 $e^{'}$
2. 將 $G_{M} - e^{'} + e$ 加入至集合 $S$ 中
$S$ 中權重和最小的樹即為所求

證明

先考慮一個樸素作法，因為次小生成樹與最小生成樹至少有一條邊不一樣，因此，可以枚舉最小生成樹的邊，將其刪除之後，再求最小生成樹，那次小生成樹必然會是這 $V - 1$ 顆樹中的其中一種。

接下來，可以證明刪掉一條邊的圖，存在一個最小生成樹，與原來的最小生成樹只有一條相異的邊。考慮 Kruskal 演算法，如果把第 $i$ 個加入最小生成樹的邊 $e_{i} = (s_{i}, t_{i})$ 刪除的話，並不影響加入第 $i$ 條邊之前的決策。接下來，將原來最小生成樹第 $i + 1$ 條邊到 $V - 1$ 條邊加入這一個新的樹中，那會得到兩個獨立的兩個連通塊 (原來MST砍掉 $s$ 到 $t$ 的邊 )，此時再找到一條最小的邊 $e^{'}$ 將這兩個連通塊接在一起，就形成了一個最小生成樹，且這顆樹只有一條邊與原來的樹不一樣。

為什麼會是最小生成樹呢？因為 $e^{'}$ 必然是 Kruskal 在 $e_{i}$ 以後才被考慮的邊，且 $e^{'}$ 不會影響加入這一條邊之後的決策。考慮這兩條邊之間的其他邊 $e_{m}$ 的決策過程：

如果 $e_{m}$ 的兩端點不連接 $s_{i}, t_{i}$ 的連通塊的話，那這條邊的決策就不被影響
如果 $e_{m}$ 的兩端點連接 $s_{i}, t_{i}$ 的連通塊的話，那這條邊就是比 $e^{'}$ 更小連接方法，那與 $e^{'}$ 的定義矛盾，因此不存在這種情形。

因此這個方法會是 Kruskal 的決策過程，故作出來的樹是最小生成樹。因此就可以推出存在一的次小生成樹，是與其最小生成樹相差一條邊的樹。

時間複雜度

步驟 1 若使用 Kruskal’s algorithm，複雜度為 $O (E \log E)$
步驟 3.1 若使用最近公共祖先 (Lowest Common Ancestor, LCA) 的倍增法，單次可以在 $O (\log V)$ 的時間求出 $e^{'}$
集合 $S$ 實作上，只需要紀錄加入及刪除哪一條邊即可，都可以在 $O (1)$ 時間完成

故可以在 $O (E \log E)$ 的時間求出次小生成樹