深度優先搜尋的應用：標記連通分量

筆記／深度優先搜尋的應用：標記連通分量

給定一個具有 $n$ 個頂點與 $m$ 條邊的無向圖 $G \comma$本文簡介如何利用深度優先搜尋在 $O(1 + n + m)$ 時間內找出 $G$ 中的連通分量。

$ \gdef\twodots{\mathinner{\ldotp\ldotp}} $

1　準備工作

對任意整數 $a \jcomma b \comma$我們定義 \[\begin{split}[a \twodots b] = \{k \in \ZZ: a \leq k \leq b\} \period\end{split}\]

設 $G$ 為一無向圖，其頂點集為 $[0 \twodots n \varminus 1] \period$

對於任意頂點 $u \jcomma v \comma$若在 $G$ 中存在連接 $u$ 與 $v$ 的路徑，則我們稱 $u$ 與 $v$ 在 $G$ 中連通。

若子圖 $H \subseteq G$ 中任兩頂點之間均連通，則我們稱 $H$ 連通。我們將 $G$ 中的極大連通子圖稱為 $G$ 的連通分量（con­nect­ed com­po­nent）。

2　演算法

對任意頂點 $u \comma$我們將在 $G$ 中與 $u$ 相鄰的頂點存在陣列 \[\begin{split}A_u[0 \twodots \allowbreak m_u \varminus 1]\end{split}\] 中，其中 $m_u$ 為與 $u$ 相鄰的頂點的個數。

演算法 A（遍歷連通分量） 給定（具有 $n$ 個頂點、$m$ 條邊的）無向圖 $G \jcomma$陣列 $C[0 \twodots n \varminus 1] \jcomma$頂點 $r \jcomma$非負整數 $k$ 與一空堆疊 $S \comma$若對每個在 $G$ 中與 $r$ 連通的頂點 $u$ 均有 $C[u] < 0 \comma$則演算法 A 會將與 $r$ 連通的頂點 $u$ 所對應的 $C[u]$ 設為 $k \period$

  1. 設 $C[r] \gets k \comma$並將 $r$ 放入堆疊 $S \period$
  2. 若 $S$ 為空，則終止演算法；否則由堆疊 $S$ 中取出一元素 $u \period$
  3. 設 $i \gets m_u - 1 \comma$並跳至步驟 6。
  4. 設 $v \gets A_u[i] \period$若 $C[v] < 0 \comma$則設 $C[v] \gets k \comma$並將 $v$ 放入堆疊 $S \period$
  5. 設 $i \gets i - 1 \period$
  6. 若 $i \geq 0 \comma$則回到步驟 4；否則回到步驟 2。

正確性　我們說明對每個頂點 $u \comma$下列敘述均成立：

  1. 若 $u$ 與 $r$ 在 $G$ 中連通，則 $u$ 在執行過程中會被放入堆疊 $S \comma$且放入堆疊的次數恰為 1 次。
  2. 若 $u$ 曾經在步驟 1 或 4 被放入堆疊 $S \comma$則 $u$ 與 $r$ 在 $G$ 中連通。

首先我們說明 (a)。我們對 $u$ 與 $r$ 在 $G$ 中的距離 $d_G(r, u)$ 使用數學歸納法。

若 $d_G(r, u) = 0 \comma$則我們有 $u = r \comma$此時 $r$ 會在步驟 1 時被放入堆疊，且由於放入堆疊後 $C[r] = k \comma$故 $r$ 不會在後續的步驟 4 被放入堆疊，即放入堆疊的次數恰為 1 次。

接著假設 (a) 在 $d_G(r, u) = d$ 時均成立。當 $d_G(r, u) = d + 1$ 時，由於 $u \neq r \comma$可知 $u$ 不會在步驟 1 時被放入堆疊。設 $u'$ 是 $u$ 在 $G$ 中的鄰居，其滿足 $d_G(r, u) = d \period$由歸納假設可知 $u'$ 曾經被放入堆疊，故當 $u'$ 在步驟 2 中被取出時，$u$ 會在後續的步驟 3―5 中恰有 1 次被設為 $v \comma$並放入堆疊。由於放入堆疊後 $C[u] = k \comma$故 $u$ 接下來不會再被放入堆疊，即放入堆疊的次數恰為 1 次。至此 (a) 得證。

接著我們說明 (b)。若 $u$ 曾在步驟 1 被放入堆疊，則 $u = r \period$以下我們考慮 $u$ 曾在步驟 4 被放入堆疊的狀況。

假設 $u$ 是在第 $t$ 次執行步驟 4 時被放入堆疊。我們對 $t$ 使用數學歸納法：若 $t = 1 \comma$則 $u$ 即為 $r$ 的鄰居。若 $t \geq 2 \comma$則 $u$ 會是一個在第 $t'$ 次執行步驟 4 時被放入堆疊的頂點 $u'$ 的鄰居，其中 $t' \in \{1 \cm 2 \cm \ldots \cm t \varminus 1\} \period$由 $u'$ 與 $r$ 連通的歸納假設可知 $u$ 與 $r$ 連通。故 (b) 得證。

由 (a)、(b) 可知被放入堆疊 $S$ 的頂點恰為所有與 $r$ 連通的頂點，且每個頂點 $u$ 被放入堆疊時 $C[u]$ 均被設為 $k \period$至此演算法的正確性得$\textrm{證。}\mkern6mu\blacksquare$

時間複雜度　由於每個與 $r$ 連通的頂點恰會被放入堆疊、取出堆疊各 1 次，可知演算法 A 的時間複雜度為 $O(1 + \lvert E(H(r)) \rvert) \comma$其中 $H(r)$ 為 $r$ 所屬的連通分$\textrm{量} \period\;\blacksquare$

演算法 B（標記連通分量） 給定具有 $n$ 個頂點、$m$ 條邊的無向圖 $G$ 與一陣列 $C[0 \twodots \allowbreak n \varminus 1] \comma$演算法 B 會將每個頂點 $u$ 所屬連通分量的編號填入 $C[u] \comma$並回傳連通分量的個數 $k \period$

  1. 設 $k \gets 0 \comma$並對每個 $u \in [0 \twodots \allowbreak n \varminus 1]$ 設 $C[u] \gets -1 \period$
  2. 配置一空堆疊 $S \comma$其最大容量為 $m \period$
  3. 設 $r \gets 0 \comma$並跳至步驟 8。
  4. 若 $C[r] < 0 \comma$則跳至步驟 7。
  5. 對無向圖 $G \jcomma$陣列 $C[0 \twodots n \varminus 1] \jcomma$頂點 $r \jcomma$整數 $k$ 與堆疊 $S$ 執行演算法 A（遍歷連通分量）。
  6. 設 $k \gets k+1 \period$
  7. 設 $r \gets r+1 \period$
  8. 若 $r \leq n-1 \comma$則回到步驟 4；否則終止演算法並回傳 $k \period$

正確性　注意到下列敘述成立：

  1. 對每個連通分量 $H \comma$均存在唯一一個會執行步驟 5 的頂點 $r \in V(\.H) \period$
  2. 若 $H \jcomma H'$ 為相異的連通分量，則在演算法終止時對任意 $u \in V(\.H)$ 與 $u' \in V(\.H')$ 均有 $C[u] \neq C[u'] \period$
  3. 演算法終止時所回傳的 $k$ 即為 $G$ 的連通分量的個數。
  4. 演算法終止時，對每個頂點 $u$ 均有 $0 \leq C[u] \leq k-1 \period$

因而演算法 B 的正確性得$\textrm{證。}\mkern6mu\blacksquare$

時間複雜度　除了步驟 5 以外，其餘步驟所需的總時間為 $O(1 + n + m) \period$假設 $G$ 中各連通分量分別為 $H_0 \cm H_1 \cm \ldots \cm H_{k-1} \period$對每個 $i \in \{0 \cm 1 \cm \ldots \cm k \varminus 1\} \comma$恰有一個頂點 $r \in V(H_i)$ 會執行步驟 5，其花費的時間為 $O(1 + \lvert E(H_i) \rvert) \period$由於 \[\begin{split}\sum_{i=0}^{k-1} (1 + \lvert E(H_i) \rvert) = k + m \leq n + m \comma\end{split}\] 故演算法 B 的總花費時間為 $O(1 + n + m) \period\;\blacksquare$

3　程式碼實作

以下為 Python 的實作。

from collections.abc import Iterable, Sequence

type Graph = Sequence[Iterable[int]]

def traverse(A: Graph, C: Sequence[int], r: int, k: int) -> None:
    C[r] = k
    S = [r]
    while S:
        u = S.pop()
        for v in A[u]:
            if C[v] < 0:
                C[v] = k
                S.append(v)

def mark_connected_components(A: Graph) -> tuple[int, list[int]]:
    n, k = len(A), 0
    C = [-1 for v in range(n)]
    for r in range(n):
        if C[r] < 0:
            traverse(A, C, r, k)
            k += 1
    return (k, C)

參考資料

  1. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to algorithms. MIT press, third edition, 2009.