無向圖可以有很多環,卻仍靠某一條邊連接兩大片區域。逐邊刪除後重跑遍歷,會重複大部分工作。一次深度優先搜尋,則能判斷每個子樹是否有另一條路返回所屬連通分量的其餘部分。
所需資訊是 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]。
重播同一個圖,觀察每次返回,並將實體刪邊結果與兩種刻意錯誤的規則比較。
判斷橋邊,需要已完成的子節點及獨立邊 ID
追蹤無向 DFS 森林,觀察 low-link 值改變,再只刪除指定 ID 的邊作核對。比較正確規則與兩種明確的錯誤。
已在初始事件。
DFS 前 · 事件 0/23
目前頂點: 無; 目前邊: 無.
邊上的數字是 ID。T 表示已發現樹邊;F 表示所選演算法目前標記的邊;P 表示刪邊核對目標。DFS 始終使用包括 P 在內的原圖。頂點顯示發現時間及目前 low;表格提供相同資訊。
DFS 堆疊:底 → 頂: 無.
此事件沒有 low 更新.
此事件沒有已完成子節點的橋邊檢查。
| 頂點 | 發現時間 tin | 目前 low | 頂點狀態 | 父頂點 | 父邊 ID |
|---|---|---|---|---|---|
| 0 | 無 | 無 | 未發現 | 無 | 無 |
| 1 | 無 | 無 | 未發現 | 無 | 無 |
| 2 | 無 | 無 | 未發現 | 無 | 無 |
| 3 | 無 | 無 | 未發現 | 無 | 無 |
| 4 | 無 | 無 | 未發現 | 無 | 無 |
| 5 | 無 | 無 | 未發現 | 無 | 無 |
| 6 | 無 | 無 | 未發現 | 無 | 無 |
| 邊 ID | 端點 | 已發現樹邊 | 目前已標記 | 按刪邊定義判斷為橋邊 | 核對邊 |
|---|---|---|---|---|---|
| 0 | (0,1) | 否 | 否 | 否 | 是 |
| 1 | (1,2) | 否 | 否 | 否 | 否 |
| 2 | (2,0) | 否 | 否 | 否 | 否 |
| 3 | (1,3) | 否 | 否 | 是 | 否 |
| 4 | (3,4) | 否 | 否 | 否 | 否 |
| 5 | (3,4) | 否 | 否 | 否 | 否 |
| 6 | (4,5) | 否 | 否 | 是 | 否 |
演算法目前標記: 無; 真正橋邊 ID: [3, 6]; 錯誤標記 ID: 無.
完成 DFS 後才檢查遺漏。
刪除一條實體邊: e0
刪除只移去該 ID 的邊。上方 DFS 仍屬原圖;下方分量標籤來自刪邊後的另一趟遍歷。
原圖連通分量數: 2; 刪除核對邊後的分量數: 2; 核對邊令分量數增加: 否.
- 頂點 0: 刪邊後分量標籤 0
- 頂點 1: 刪邊後分量標籤 0
- 頂點 2: 刪邊後分量標籤 0
- 頂點 3: 刪邊後分量標籤 0
- 頂點 4: 刪邊後分量標籤 0
- 頂點 5: 刪邊後分量標籤 0
- 頂點 6: 刪邊後分量標籤 1
刪除所有真正橋邊後的分量數: 4 = 2 + 2.
此數量使用定義中的真正橋邊,與錯誤 DFS 標記無關;它等於原分量數加真正橋邊數。
完整 DFS 事件追蹤
| 事件 | 動作 | 目前頂點 | 目前邊 | 已檢查鄰接項數 | 子節點檢查:low 與父 tin | 事件後標記 |
|---|---|---|---|---|---|---|
| DFS 前 | 無 | 無 | 0 | 無 | 無 | |
| 發現新分量的根 | 0 | 無 | 0 | 無 | 無 | |
| 沿樹邊發現子節點 | 1 | 0 | 1 | 無 | 無 | |
| 略過父連接 | 1 | 0 | 2 | 無 | 無 | |
| 沿樹邊發現子節點 | 2 | 1 | 3 | 無 | 無 | |
| 略過父連接 | 2 | 1 | 4 | 無 | 無 | |
| 檢查已發現的鄰點 | 2 | 2 | 5 | 無 | 無 | |
| 完成子節點、傳回 low 並檢查父邊 | 2 | 1 | 5 | 0 > 1: 否 | 無 | |
| 沿樹邊發現子節點 | 3 | 3 | 6 | 無 | 無 | |
| 略過父連接 | 3 | 3 | 7 | 無 | 無 | |
| 沿樹邊發現子節點 | 4 | 4 | 8 | 無 | 無 | |
| 略過父連接 | 4 | 4 | 9 | 無 | 無 | |
| 檢查已發現的鄰點 | 4 | 5 | 10 | 無 | 無 | |
| 沿樹邊發現子節點 | 5 | 6 | 11 | 無 | 無 | |
| 略過父連接 | 5 | 6 | 12 | 無 | 無 | |
| 完成子節點、傳回 low 並檢查父邊 | 5 | 6 | 12 | 5 > 4: 是 | [6] | |
| 完成子節點、傳回 low 並檢查父邊 | 4 | 4 | 12 | 3 > 3: 否 | [6] | |
| 檢查已發現的鄰點 | 3 | 5 | 13 | 無 | [6] | |
| 完成子節點、傳回 low 並檢查父邊 | 3 | 3 | 13 | 3 > 1: 是 | [3, 6] | |
| 完成子節點、傳回 low 並檢查父邊 | 1 | 0 | 13 | 0 > 0: 否 | [3, 6] | |
| 檢查已發現的鄰點 | 0 | 2 | 14 | 無 | [3, 6] | |
| 完成根節點 | 0 | 無 | 14 | 無 | [3, 6] | |
| 發現新分量的根 | 6 | 無 | 14 | 無 | [3, 6] | |
| 完成根節點 | 6 | 無 | 14 | 無 | [3, 6] |
- 已檢查鄰接項數
- 0
- 鄰接項總數
- 14
- 演算法目前標記
- 無
- 真正橋邊 ID
- [3, 6]
- 原圖連通分量數
- 2
- 刪除核對邊後的分量數
- 2
- 核對邊令分量數增加
- 否
- 最終標記符合定義
- DFS 未完成
事件 0/23: DFS 前. 目前頂點: 無; 目前邊: 無. 演算法目前標記: 無; 最終標記符合定義: DFS 未完成. 核對邊: e0; 原圖連通分量數: 2; 刪除核對邊後的分量數: 2; 核對邊令分量數增加: 否.
為何這些資訊能證明橋邊
橋邊是刪除後令連通分量數增加的邊。若原圖已不連通,刪除後仍不連通並不足夠。當且僅當移去該邊後,端點仍有另一條路徑,它才不是橋邊;自環的端點具有長度零的替代路徑。
low[v] 是從 v 沿零條或多條 DFS 樹邊向下,再至多沿一條非樹邊到祖先,可達的最小發現時間。初值為 tin[v]。已發現鄰點提供其發現時間;已完成子節點提供其完整 low。頂點仍進行中時,後代可能找到逃出路徑,使顯示的值繼續下降。
對樹邊 u→v,當且僅當 low[v]≤tin[u],才有另一條邊由 v 的子樹跨至 u 或其祖先,可繞過 u→v。若 low[v]>tin[u],樹邊就是這道切割的唯一連接,刪除便分裂該分量。相等已表示能回到 u 本身;把 > 改為 ≥ 因而會捏造橋邊。
頂點 0、1 之間若有平行邊 0、1,DFS 可沿邊 0 進入子節點。子節點只略過邊 0;邊 1 是另一條回到父頂點的路徑,會把子 low 降至父發現時間。若略過所有通往父頂點的邊,就會丟掉這條路徑,錯誤標記邊 0。刪除任一實體邊,另一條仍存在。
例題圖的已完成 low 為 [0,0,0,3,3,5,6],真正橋邊 ID 為 [3,6]。平行邊使 low[4]=tin[3]=3,因此邊 4 不是橋邊。孤立頂點 6 需要另一個 DFS 根。原分量數為 2;刪除任一真正橋邊變成 3,兩條都刪除後有 4 個區域。收縮各區域後得到森林。
每個頂點只發現一次;每條無向邊,包括自環,都有兩個鄰接項。演算法各檢查一次,並只在子節點傳回時檢查父邊,工作量為 O(V+E)。追蹤快照、繪圖及反覆刪邊核對是額外的教學診斷,不計入該 DFS 界限。發現時間和 low 依賴遍歷次序,真正橋邊集合則不變。
low[子]=tin[父] 時,父邊可能是橋邊嗎?
不會。相等證明存在另一條路回到父頂點,沒有重用該樹邊;平行邊例子中的另一條邊就是這條路徑。橋邊的嚴格比較與割點判準不同:刪除邊和刪除頂點是兩個問題。
頂點及邊 ID 由零開始。根按頂點遞增次序處理,鄰接項按輸入次序處理,與正文一致。標記按邊 ID 排列,已完成值與暫時值有清楚區別。本圖處理無向圖,包括平行邊、自環及不連通圖;不實作割點或有向強連通分量演算法。
迭代實作必須保留「子樹返回」事件
以下使用有效整數標號 ,邊按輸入位置編號。每個堆疊框架記錄節點及下一個鄰接索引。下降前先推進父框架索引;子框架完成時,才更新父低鏈值並檢查橋,對應遞歸 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
共有 個。刪邊只會移除路徑,不會創造路徑,所以每條剩餘原橋仍沒有替代端點路徑,每次分量數加一。縮起七個區域、保留四橋,得到具有三個連通分量的森林。