Leetcode 1489: Find Critical and Pseudo-Critical Edges in Minimum Spanning Tree
Published in
Dec 6, 2021
Difficulty: Hard, (8 personal rank)
Keywords: Tarjan algo, bridge, DSU, Kruskal algo, MST
預備知識
- DSU, Tarjan’s algorithm, Kruskal’s algorithm
題目
給一個無向有權的聯通圖，問哪些邊是critical，哪些邊是pseudo-critical。定義
- critical edge：從圖中去掉該邊，會導致MST的成本上升
- pseudo-critical edge：他可以出現在至少一個MST中而不導致MST的成本上升
解法一 (窮舉所有邊)
- 找critical edges：由於critical edge從圖中拿走的話，會導致MST的成本上升，根據這個想法把每個邊都窮舉一次看看MST的成本是否變化即可知道是否為critical edge
- 找pseudo-critical edges，一種很直覺的想法是，這條邊一定要第一個納入MST中，爾後才跑Kruskal’s algo找MST，如果MST的成本在有這條邊的情況之下沒有上升，且這條邊不是critical edge，意味著這條邊就是pseudo-critical edge。
複雜度
- 時間複雜度：事先sort好所有邊，對每條邊都跑兩次Kruskal：O(E²)
解法二 (Kruskal的過程中，基於當前的聯通子圖，挑選出bridges)
回顧一下Kruskal的作法，對所有邊依照權重從小到大排序，並逐一嘗試放入MST中，如果當前邊的兩側，透過並查集確認來自不同的聯通塊，則這條邊便可以是MST的其中一條，反之則不屬於MST。
假設我們已經處理完權重在w之下的所有邊，並形成一個當前的子圖，該子圖的聯通性可以透過DSU目前的狀態得知，並將每個連通分量視為一個點，如果難以想像什麼是將連通分量視為一個點，請參考下圖：
總之此時我們會同時處理所有權重等於w的邊，並將這些邊分為兩種情況：
- 這條邊的兩側來自於當前同一個點(黃邊)，顯然該邊在目前的子圖中自環，不會是MST的一部分，可以直接捨棄
- 兩側來自於不同點(紅或藍邊)，此時這條邊可能是pseudo-critical或是critical，總之我們知道這條邊是我們需要的邊，並先保存下來。
為了確認當前子圖中，被保存的邊哪些是critical edges，我們可以在這些邊中找到bridges。所謂bridge就是在一個圖中，捨棄它會導致圖的聯通性被破壞的邊。我們很容易從圖中看出紅邊才是bridge，藍邊則是pseudo-critical edges。
複雜度
排序花費O(E*log(E))，對每個權重都跑一次Tarjan_w：O(E_w + V_w)，由於 V_w <= 2E_w，又sum_w(E_w) = E，因此所有Tarjan的總時間複雜度為O(E)
- 總時間複雜度：O(E*log(E))
- 總空間複雜度：O(E + V)
程式碼
要注意重邊必然不是橋，在Tarjan算法中無法判斷這件事情，需要自己去把重邊挑出來。
