次小生成樹

定義

考慮一張無向的加權圖G={V,E,cost(s,t)}中，在G的生成樹中，權重非嚴格第二小的生成樹

演算法

1. 先找出G的最小生成樹 Gm

2. 定義集合 S = {}

3. 對於所有不在最小生成樹裡面的邊 e={s,t}

   1. 找出在 Gm 中 s 到 t 的路徑中權重最大的邊 e'

   2. 將 GM - e' + e 加入 S

4. S 中權重最小的生成樹就是次小生成樹

證明

考慮一個最樸素的做法，次小生成樹一定至少有一個邊與最小生成樹不同，所以我們可以枚舉最小生成樹的邊，將邊拔掉之後，產生一個新的最小生成樹，而這個最小生成樹就會是與原本的最小生成樹相差一個邊的樹。

接下來要證明原本的最小生成樹拔掉一個邊之後，可以產生新的最小生成樹。根據 Kruskal's algorithm，一個邊是連結兩個MSS中唯一的邊，所以刪除該邊之後，會產生兩個新的MSS，之後再將兩個MSS用新的權重最小的邊連結就產生了一個新的MST，而這個MST只會跟原本的MST相差一條邊。

這樣的作法如果枚舉的是所有的邊，並且產生生成樹使用的是Kruskal演算法，複雜度會是O(VElogE)，事實上有更小複雜度的做法，在找到原圖的MST之後，我們可以枚舉所有不在MST裡面的邊，將新的邊e={s,t}加入MST之後必定會產生一個新的環，在此環上我們可以找到次大的邊e'={s',t'}(除了E以外最大的邊)刪除，而刪除後這整個圖還會是連通的，而新的圖的權重就會是MST的權重檢掉刪除邊的權重加上E的權重，

weight of newMST = MST - weight of e' + weight of e

這樣的複雜度會是:

• 找到一個MST O(ElogE)

• 枚舉不在MST的邊 O(E)

  • 找到環裡面次小的邊 O(V)

• 在S中只要記錄當中權重和最小的MST的權重就好了 O(1)

整體複雜度 O(ElogE + EV)

但這樣的話不足以解掉c495: 四、次小生成樹(SBMST)

考慮到步驟3

如果使用的是 最近公共祖先 (Lowest Common Ancestor, LCA) 的倍增法，單次可以在 O(logV) 的時間求出 e^′ (預處理O(VlogV))

這樣新的複雜度就是 O(ElogE + VlogV + ElogV) ，就可以開心的解掉 c495 了

最近公共祖先 (Lowest Common Ancestor, LCA)

倍增法LCA:

• 求出每個點的祖先，祖先的祖先(第2祖先)，第4祖先，第8祖先 ......

• 利用一次 dfs 求出各點的 2^i 次方祖先，深度，路徑上的最大權重

  • parent[i][u] 代表 u 的第 2^i 祖先

  • depth[u] 代表 u 在 dfs 樹上的深度

  • maxcost[i][u] 代表 u 在往第 2^i 祖先上最大的權重

• 尋找u, v的LCA

  • 假設 u 的深度小於 v 的深度 (u 比 v還要高)

  • 找到v的其中一個祖先v' 使得 depth[v'] == depth[u]

    • 如果 v' == u 代表 u 就直接是 u,v 的LCA

    • 如果 v' != u

      • 尋找 u, v' 的第1, 2, 4, 8 ......祖先，由於一定會有一個LCA，假設該LCA與 u, v' 深度相差 D，求1, 2, 4, 8... 的過程相當於將D以2進位表示

      • 過程中不斷更新當前遇到的最大權重 maxweight

程式碼