無向圖可以有很多環,卻仍靠某一條邊連接兩大片區域。逐邊刪除後重跑遍歷,會重複大部分工作。一次深度優先搜尋,則能判斷每個子樹是否有另一條路返回所屬連通分量的其餘部分。
所需資訊是 low-link 低鏈值。理解其意義,才知道為何橋判準使用嚴格比較。邊的身分也很重要:端點相同的兩條邊是不同路線,若把它們都當成「父連線」跳過,便可能憑空報告一條橋。
相對於原有分量數定義邊失效
定義 10.1.1
(無向多重圖中的橋)
設 為有限無向圖,容許平行邊及自環,每條邊具有獨立 ID。刪邊只刪該條具體邊。若刪除令連通分量數增加,便稱該邊為橋,亦稱割邊。
圖原本可以不連通,所以不能只檢查刪後是否不連通,必須比較分量數是否增加。自環不會改變不同節點間的連通,故永遠不是橋。
證明透視
橋恰好是沒有另一條端點路徑的邊
設邊 端點為 。若刪除後仍有 到 路徑,原本經過 的任何路線都可用該路徑替換,所以原有分量不會分裂, 不是橋。
反過來,若刪後兩端點分離,其原有分量已分裂,分量數增加。對自環,端點到自身的零長路徑就是另一條端點路徑。
一條邊最多把舊分量分成兩部分:由任意節點到 的原有簡單路徑,若不經 就仍連到 ;若經 ,跨越前已到 ,所以仍連到 。因此,橋令分量數恰好加一。
端點不同時,可選簡單替代路徑,與 合成一個環;反過來,包含 的環,其餘部分就是替代路徑。約定自環為長一的環,兩條平行邊為長二的環,便有:一條邊是橋,充要條件是它不在任何環上。
DFS 樹限制了逃出子樹的邊能去哪裏
執行深度優先搜尋,每遇未訪節點就建立新根。首次發現節點時,以遞增全局計數器記 。發現新節點的邊形成 DFS 森林,某節點及其森林後代構成其子樹。
無向 DFS 的每條非樹邊都連接祖先與後代,自環視為退化情況。兩棵互非祖先的已完成子樹之間不會有邊:較早子樹檢查該邊時,本來就會在完成前發現另一端。
因此,離開某個子樹的其他邊必須連到祖先。這個結構事實令最小發現時間能作為逃出證明。
定義 10.1.2
(低鏈值的意義與遞歸式)
是以下路線可達的最小發現時間:由 開始,沿零條或多條 DFS 樹邊向下,然後至多使用一條非樹邊到祖先,也容許完全不移動。
先設 。對 DFS 子節點 ,待其遍歷完成後,以 更新最小值。若經非父邊遇到已發現鄰點 ,則以 更新。
證明透視
每次更新都對應一條允許路線
初始值代表留在 。若路線先沿樹邊走到子節點 ,餘下正由 總結,因此必須使用子樹完成後的值。
由 沿非樹邊到祖先 ,直接得到 。從祖先端檢查邊時,也可能遇到已訪後代;其發現時間大於 ,不會降低目前值,作同樣最小更新也無害。
每條允許向下路線,不是留在當前節點,就是先進入某個子樹。這些情況涵蓋定義,對 DFS 返回事件作歸納便證明遞歸式。必須排除具體的父樹邊,因立即經待檢查邊返回,不是另一條路。
低鏈值是發現時間,不是分量大小、回邊數或最短路徑長度。所有後代處理完畢後,子節點的值才完整。
常見錯誤
(在子節點返回之前就測試)
子節點的 low 值要等到它的所有後代都處理完才是最終值。在從 出發探索的三角形 中,頂點 2 的初始值是 。若用這個初始值對 作測試,會把邊 當成橋;但 2 到 0 的非樹邊把 降到 ,所以它不是橋。
橋判準使用嚴格不等式
定理 10.1.3
(DFS 樹邊的橋判準)
設 為從 到其 DFS 子節點 的樹邊。則 是橋,當且僅當 。每條非樹邊(包括自環)都在某個環上,所以不是橋。
證明透視
父 u 到子 v 的樹邊是橋,恰好當 low[v] 大於 tin[u]
設 是 的 DFS 子節點,把 整棵子樹與所屬分量其餘部分分開,得到一個割。父樹邊跨越此割;任何其他跨割邊,必須由 後代經非樹邊連到 或 的祖先。
存在這種邊,恰好等價於 。由子樹內走到該邊,跨到祖先一側,再使用那一側的樹路徑,就能繞過父樹邊。因此它不是橋。
若 ,沒有其他跨割邊。刪除父樹邊便分離整棵子樹,所以是橋。非樹邊本身與一條樹路徑成環,不可能是橋。
相等情況不可忽略: 表示有另一條路返回 本身,已足夠繞過樹邊。用 取代 ,會錯報這些環邊。
跳過父邊,不是跳過全部連到父節點的邊
反例模式
平行邊揭示兩者差別
節點零與一之間有 ID 零、一兩條平行邊。DFS 經邊零發現節點一。在子節點只跳過邊零,因它是父樹邊的反向鄰接項。邊一仍返回節點零,使 降至 。
兩條都不是橋,刪任一條都還有另一條。若程式因鄰點等於父節點便全部跳過,就會跳過兩條,令低鏈值錯誤偏高,把樹邊誤報為橋。
獨立邊 ID 保留了父邊與平行替代路線的具體差別。
追蹤含孤立節點的完整例子
例題 10.1.4
(一個環、一條橋、平行邊及另一條橋)
使用節點零至六,輸入邊依次為:
| 邊 ID | 端點 | 在圖中的角色 |
|---|---|---|
| 第一個三角形 | ||
| 第一個三角形 | ||
| 第一個三角形 | ||
| 連到平行邊區域 | ||
| 其中一條平行邊 | ||
| 另一條平行邊 | ||
| 連到節點五 |
節點六孤立。根按遞增次序、鄰接項按輸入次序處理,得到:
| 節點 | 發現時間 | 完成後低鏈值 |
|---|---|---|
三角形的二到零邊,把節點二降至零,再傳到節點一。第二條平行邊把節點四降至發現時間三,所以樹邊四是相等情況,不是橋。節點五沒有逃出路,邊六是橋;同樣 ,邊三也是橋。
橋 ID 為 [3, 6]。孤立節點需要另一個 DFS 根,卻沒有父邊可檢查。
例題 10.1.5
(自環與一條路徑)
取 及編號 的邊:、、。在頂點 0,自環的邊端編號為 ,不是父邊,而且端點已被發現,所以它把 貢獻給 ,而 本來就是 。樹是鏈 ,,且 、。邊 2 有 ,邊 1 有 ,所以兩者都是橋。自環從不作為樹邊被測試,也不是橋。橋的 ID 為 [1, 2]。
重播同一個圖,觀察每次返回,並將實體刪邊結果與兩種刻意錯誤的規則比較。
迭代實作必須保留「子樹返回」事件
以下使用有效整數標號 ,邊按輸入位置編號。每個堆疊框架記錄節點及下一個鄰接索引。下降前先推進父框架索引;子框架完成時,才更新父低鏈值並檢查橋,對應遞歸 DFS 返回。
def bridge_edges(n, edges):
if n < 0:
raise ValueError("vertex count must be nonnegative")
edges = list(edges)
adjacency = [[] for _ in range(n)]
for edge_id, (u, v) in enumerate(edges):
if not (0 <= u < n and 0 <= v < n):
raise IndexError("edge endpoint outside the vertex set")
adjacency[u].append((v, edge_id))
adjacency[v].append((u, edge_id))
tin = [-1] * n
low = [-1] * n
parent = [-1] * n
parent_edge = [-1] * n
is_bridge = [False] * len(edges)
timer = 0
for root in range(n):
if tin[root] != -1:
continue
tin[root] = low[root] = timer
timer += 1
stack = [(root, 0)]
while stack:
vertex, next_index = stack[-1]
if next_index == len(adjacency[vertex]):
stack.pop()
edge_id = parent_edge[vertex]
if edge_id != -1:
predecessor = parent[vertex]
low[predecessor] = min(low[predecessor], low[vertex])
if low[vertex] > tin[predecessor]:
is_bridge[edge_id] = True
continue
stack[-1] = (vertex, next_index + 1)
neighbor, edge_id = adjacency[vertex][next_index]
if edge_id == parent_edge[vertex]:
continue
if tin[neighbor] != -1:
low[vertex] = min(low[vertex], tin[neighbor])
else:
parent[neighbor] = vertex
parent_edge[neighbor] = edge_id
tin[neighbor] = low[neighbor] = timer
timer += 1
stack.append((neighbor, 0))
bridge_ids = [edge_id for edge_id, flag in enumerate(is_bridge) if flag]
return bridge_ids, tin, low
每個節點只發現一次,每條無向邊貢獻兩個鄰接項,自環亦然,每項只檢查一次。堆疊操作、低鏈更新及邊旗標每次都是常數工作。最後線性掃描按輸入次序輸出橋 ID,不需排序。總時間及空間均為 。明確堆疊也避免長路徑的遞歸調用深度限制。
回傳的低鏈值依賴 DFS 次序,橋集合則是圖本身的性質。改動鄰接次序,可以改變發現時間及低鏈值,卻不改變哪些邊是橋。
刪除橋,顯示區域之間的森林
定理 10.1.6
(橋森林)
設 有 個連通分量和 條橋。刪去所有橋後恰好剩下 個分量,而且其中沒有分量含橋。把每個餘下的分量縮成一個頂點,再放回各條橋,得到一個森林。
證明
(縮合無橋區域)
原圖有 個連通分量、 條橋。刪掉全部橋後再找分量。刪過其他橋後,每條剩餘原橋仍是橋,因刪邊不會創造新的替代路徑。每次分量數加一,所以最後有 個分量。
每條原非橋邊都在某個環上,而環上不可能有原橋。這些環刪橋後仍完整,所以餘下分量內沒有橋。
把每個餘下分量縮成一個節點,再恢復原橋,得到森林。若縮點後有環,把分量內路徑展開,就能繞過環上的某條原橋,與橋的性質矛盾。
例子中 ,得到四個區域:、、、。橋森林是一條三節點路徑,加一個孤立節點。
反例模式
割點是另一種失效對象
取共享節點二的兩個三角形: 及 。每邊都在三角形上,所以沒有橋。但刪除節點二及全部相鄰邊後, 與 分開,因此二是割點。
橋檢查刪一條邊;割點檢查刪節點及其全部相鄰邊。嚴格橋判準本身沒有提供割點算法。
常見錯誤
(邊與頂點的測試用了同一個門檻)
對從 到 的樹邊,橋需要嚴格的 ,因為回到 本身的路已經繞過該邊。對割點 ,子節點 把子樹分開的條件是 ,因為刪去 同時毀掉只回到 的路。對邊 加兩條 ,等式 說明 不是橋,但頂點 1 是割點。
練習與詳解
快速檢查
(1. 比較分量數,不只看是否不連通)
原圖已有兩個分量,刪某邊後仍有兩個,該邊是橋嗎?若變成三個呢?
解答 · 解答 1
仍是兩個,便不是橋;增至三個,就是橋。定義比較前後,原本不連通的圖也可同時包含橋與非橋。
快速檢查
(2. 正確解讀相等情況)
樹邊由 到子節點 ,、。它是橋嗎?相等證明了甚麼?
解答 · 解答 2
不是橋。有後代路線經非樹邊回到 ,不使用父樹邊。回到 本身已足夠,不必到它更高祖先。因此用 ,不能用 。
快速檢查
(3. 保留平行替代路線)
兩節點有兩條平行邊,DFS 用第一條作樹邊。子節點應跳過哪個鄰接項?第二條如何影響低鏈值?
解答 · 解答 3
只跳過第一條的 ID。第二條仍是回父節點的非樹路線,令子低鏈值降至父發現時間。兩條都不是橋,因另一條在刪除後仍然存在。
快速檢查
(4. 完成例子的橋測試)
用完成後數值,檢查七節點例子的樹邊三、四、六。為何必須等子節點完成才測試?
解答 · 解答 4
邊三有 ,是橋;邊四有 ,不是;邊六有 ,是橋。後代可能發現逃出邊並降低子低鏈值,返回前使用未完成數值,可能誤報橋。
快速檢查
(5. 分清邊失效與節點失效)
兩個三角形共享一點,為何沒有橋卻有割點?自環會增加一條橋嗎?
解答 · 解答 5
每邊都有三角形其餘路線作替代,但共享節點是兩三角形唯一共同連接,刪掉它就分離。自環不連接不同節點,刪後不會增加分量數,永遠不是橋。
快速檢查
(6. 刪光橋後計算區域數)
原圖三個分量、四條橋,全部刪除後有多少分量?為何先刪某橋,不會為後來的橋創造替代路徑?
解答 · 解答 6
共有 個。刪邊只會移除路徑,不會創造路徑,所以每條剩餘原橋仍沒有替代端點路徑,每次分量數加一。縮起七個區域、保留四橋,得到具有三個連通分量的森林。