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

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

2024-08-14

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

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$ 的連通分量（connected component）。

2　演算法

對任意頂點 $u \comma$我們將在 $G$ 中與 $u$ 相鄰的頂點存在陣列 \[\begin{split}A_{\.u}[0 \twodots \allowbreak D[u] \varminus 1]\end{split}\] 中，其中 $D[u] = \lvert N_G(u) \rvert$ 為 $u$ 在 $G$ 中的度數。

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

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

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

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

首先我們說明 (a)。我們對 $r$ 與 $u$ 在 $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 \geq 0 \comma$故 $u$ 在後續的步驟 4 不會再被放入堆疊，即放入堆疊的次數恰為 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'$ 的鄰居，其中 $1 \leq t' \leq t - 1 \period$由 $u'$ 與 $r$ 連通可知 $u$ 與 $r$ 連通。故 (b) 得證。

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

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

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

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

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

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

首先說明 (a)：對連通分量 $H \comma$設 $r_H \in V(\.H)$ 為 $V(\.H)$ 中的最小值。在演算法執行過程中，若在 $r = r_H$ 時進入步驟 4，則此時由於 $C[r] = -1 \comma$因此會執行步驟 5，且在執行完步驟 5 後對每個頂點 $u \in V(\.H)$ 均有 $C[u] = k \geq 0 \period$接著若在 $r > r_H$ 且 $r \in V(\.H)$ 時進入步驟 4，則此時由於 $C[r] \geq 0 \comma$因此就不會執行步驟 5。

接著說明 (b)：不失一般性地假設 $r_H < r_{H'} \period$此時我們會有 $C[r_H] < C[r_{H'}] \comma$即對每個 $u \in V(\.H)$ 與 $u' \in V(\.H')$ 均有 $C[u] = C[r_H] < C[r_{H'}] = C[u'] \period$

接著說明 (c)：每執行一次步驟 5 之後，在步驟 6 中 $k$ 的值就會增加 1。因而由 (a) 可知 (c) 會成立。

最後說明 (d)：在執行完步驟 5 之後，$k$ 的值即為當時已標記的連通分量的個數減 1。因此，若頂點 $u$ 所屬的連通分量是第 $t$ 個被標記的連通分量，在演算法終止時即有 $C[u] = t-1 \comma$其中 $1 \leq t \leq k \period$

因而演算法 B 的正確性得證。

時間複雜度　除了步驟 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$

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)

參考資料

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

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

1 準備工作

2 演算法

3 程式碼實作

參考資料

1　準備工作

2　演算法

3　程式碼實作