摘要訊息 : 最複雜的資料結構.

0. 前言

我們已經完成了對樹 (https://jonny.vip/tag/樹/) 的探索, 接下來我們要學習資料結構中最後一個結構——圖. 圖中的有一些問題甚至比樹中的某些應用還要經典, 而且有不少臭名昭著的 NP 問題本質上都可以描述為圖中的某個問題.

本文的目錄中的標題過長, 故本篇文章的目錄預設為隱藏不展開狀態, 需要閣下手動展開.

1. 定義

定義 1. 設有向量 \boldsymbol {\alpha}_{0} = \left \{ \alpha_{1}, \alpha_{2}, ..., \alpha_{n} : n \geq 0 \right \} 的擴展 \displaystyle {\mathcal {G} = \left \{ \left ( \alpha_{1}, (e_{1}^{1}, e_{2}^{1}, ..., e_{m_{1}}^{1}) \right ), \left ( \alpha_{2}, (e_{1}^{2}, e_{2}^{2}, ..., e_{m_{2}}^{2}) \right ), ..., \left ( \alpha_{n}, (e_{1}^{n}, e_{2}^{n}, ..., e_{m_{n}}^{n}) \right ) \right \}}. 記 v_{i} = \left ( \alpha_{i}, (e_{1}^{i}, e_{2}^{i}, ..., e_{m_{i}}^{i}) \right ), 我們稱 v_{i} 是一個頂點 (vertex), e_{1}^{i}, e_{2}^{i}, ..., e_{m_{i}}^{i} 是和 v_{i} 相關的邊 (edge). 若邊 e_{k}^{i} 連接著頂點 v_{i} 和 v_{j}, 且不論從 v_{i} 出發還是從 v_{j} 出發, 都能通過邊 e_{k}^{i} 到達另外一個頂點, 那麼我們稱 \mathcal {G} 為無向圖 (undirected graph). 其中, m_{i} 是頂點 v_{i} 擁有邊的數量; i, j = 1, 2, ..., n; k = 1, 2, ..., m_{i}.

仔細觀察 Figure 1, 我們可以發現這兩個圖實際上是一樣的. 所以對於任意圖 \mathcal {G} 來說, 其平面表達其實有無限多種, 因為圖沒有限制頂點在平面上的具體位置.

定義 2. 設有向量 \boldsymbol {\alpha}_{0} = \left \{ \alpha_{1}, \alpha_{2}, ..., \alpha_{n} : n \geq 0 \right \} 的擴展 \displaystyle {\mathcal {G} = \left \{ \left ( \alpha_{1}, \left ( \overrightarrow {e_{1}^{1}}, \overrightarrow {e_{2}^{1}}, ..., \overrightarrow {e_{m_{1}}^{1}} \right ) \right ), \left ( \alpha_{2}, \left ( \overrightarrow {e_{1}^{2}}, \overrightarrow {e_{2}^{2}}, ..., \overrightarrow {e_{m_{2}}^{2}} \right ) \right ), ..., \left ( \alpha_{n}, \left ( \overrightarrow {e_{1}^{n}}, \overrightarrow {e_{2}^{n}}, ..., \overrightarrow {e_{m_{n}}^{n}} \right ) \right ) \right \}}. 記 v_{k} = \left ( \alpha_{i}, \left ( \overrightarrow {e_{1}^{k}}, \overrightarrow {e_{2}^{k}}, ..., \overrightarrow {e_{m_{k}}^{k}} \right ) \right ), 我們稱 v_{k} 是一個頂點, \overrightarrow {e_{1}^{k}}, \overrightarrow {e_{2}^{k}}, ..., \overrightarrow {e_{m_{i}}^{k}} 是和 v_{k} 相關的邊. 若邊 \overrightarrow {e_{i}^{k}} 從頂點 v_{k} 出發和 v_{j} 連接, 且通過邊 \overrightarrow {e_{i}^{k}} 只能從 v_{i} 到達 v_{j}, 無法從 v_{j} 出發通過邊 \overrightarrow {e_{i}^{k}} 到達 v_{i}, 那麼我們稱 \mathcal {G} 為有向圖 (directed graph). 其中, m_{i} 是頂點 v_{i} 擁有邊的數量; k, j = 1, 2, ..., n; i = 1, 2, ..., m_{i}.

定義 3. 無向圖的邊稱為無向邊 (undirected edge), 有向圖的邊稱為有向邊 (directed edge). 若無向邊 e 連接著頂點 v_{i} 和 v_{j}, 那麼 e 又可以寫為 [v_{i}, v_{j}]. 若有向邊 \overrightarrow {e} 從頂點 v_{i} 出發連接向 v_{j}, 那麼 \overrightarrow {e} 又可以寫為 \text {<} v_{i}, v_{j} \text {>}.

根據定義 3, 對於無向邊 e 的另一種表示方法 [v_{i}, v_{j}], 顯然 [v_{j}, v_{i}] 也可以用來表示 e, 兩者之間是等價的. 為了方便表示, 若沒有指明 e 是否有方向, 那麼我們統一用 (v_{i}, v_{j}) 來表示 e 連接的兩個頂點.

通常來說, 我們會把一個圖 \mathcal {G} 中的頂點表示為一個集合 V, 邊也表示為一個集合 E. 此時, \mathcal {G} 就可以用 (V, E) 來表示, 即 \displaystyle {\mathcal {G} = (V, E)}.

通過 Figure 1 和 Figure 2, 我們可以發現一個圖的表達不僅僅有一種. 如果一個圖的邊可以被無交叉地畫在平面上, 那麼我們就可以稱這個圖為平面圖 (planar graph).

定義 4. 無向圖和有向圖統稱為圖 (graph), 若某個圖 \mathcal {G} 既有無向邊也有有向邊, 那麼稱 \mathcal {G} 為混合圖 (mixed graph).

定義 5. 我們稱邊 e = (v_{i}, v_{i}) 為自環 (loop, 簡稱為環).

定義 6. 若頂點 v_{i} 的邊集合中, 存在多條邊 e_{j_{1}}^{i}, e_{j_{2}}^{i}, ..., e_{j_{k}}^{i} 都是連接向頂點 v_{j} 的, 即 \displaystyle {e_{j_{1}}^{i} = e_{j_{2}}^{i} = ... e_{j_{k}}^{i}}, 那麼我們稱這 k 條邊為平行邊 (parallel edge).

對於有向圖來說, 只有頂點和邊的方向完全相同的兩條邊才可以稱作平行邊. 例如 Figure 2 中, 連接 v_{2} 和 v_{3} 的兩條有向邊就不是平行邊, 雖然連接的頂點是相同的, 但是方向不同.

一般來說, 我們所說的圖都是不帶有平行邊的圖.

定義 7. 對於頂點 v_{i} = \left ( \alpha_{i}, (e_{1}^{i}, e_{2}^{i}, ..., e_{m_{i}}^{i}) \right ), 我們稱邊 e_{j}^{i} 連向的頂點為 v_{i} 的鄰居 (neighbor).

對於有向圖來說, 如果邊 \overrightarrow {e_{i}} 是從頂點 v_{i} 連向 v_{j} 的, 那麼我們可以說 v_{j} 是 v_{i} 的鄰居. 若圖中不存在從 v_{j} 連向 v_{i} 的有向邊, 那麼我們不能說 v_{i} 是 v_{j} 的鄰居. 拓展一下, 我們也可以稱 v_{i} 為 v_{j} 的廣義鄰居 (generalized neighbor).

定義 8. 稱圖 \mathcal {G} 的擴展 \mathcal {G}_{W} = \Big \{ \Big ( \alpha_{1}, \big ( (e_{1}^{1}, w_{1}^{1}), (e_{2}^{1}, w_{2}^{1}), ..., (e_{m_{1}}^{1}, w_{m_{1}}^{1}) \big ) \Big ), \\ \Big ( \alpha_{2}, \big ( (e_{1}^{2}, w_{1}^{2}), (e_{2}^{2}, w_{2}^{2}), ..., (e_{m_{2}}^{2}, w_{m_{2}}^{2}) \big ) \Big ), ..., \Big ( \alpha_{n}, \big ( (e_{1}^{n}, w_{1}^{n}), (e_{2}^{n}, w_{2}^{n}), ..., (e_{m_{n}}^{n}, w_{m_{n}}^{n}) \big ) \Big ) \Big \} 為賦權圖 (weighted graph). 其中, w_{i}^{j} 是關於邊 e_{i}^{j} 的權重. \mathcal {G}_{W} 可以簡記為 \mathcal {G}_{W} = (V, E, W).

定義 9. 我們稱 P(v_{1}, v_{n}) = v_{1} \xrightarrow {e_{i_{1}}} v_{2} \xrightarrow {e_{i_{2}}} ... \xrightarrow {e_{i_{n - 1}}} v_{n} 為圖 \mathcal {G} = (V, E) 中的鏈 (chain). 如果 \mathcal {G} 是無向圖, 那麼可以將 P(v_{1}, v_{n}) 寫為 v_{1} \xleftrightarrow {e_{i_{1}}} v_{2} \xleftrightarrow {e_{i_{2}}} ... \xleftrightarrow {e_{i_{n - 1}}} v_{n}. 若 e_{i_{1}}, e_{i_{2}}, ..., e_{i_{n - 1}} 互不相同, 則稱 P 為軌跡 (trace); 若 v_{1}, v_{2}, ..., v_{n} 互不相同, 則稱 P 為路徑 (path). 若 v_{n} = v_{1}, 則稱 P 為迴路 (circuit). 其中, v_{1}, v_{2}, ..., v_{n} \in V, e_{i_{1}}, e_{i_{2}}, ..., e_{i_{n - 1}} \in E.

一般來說, 頂點 v_{i} 到 v_{j} 的距離就是路徑 P(v_{i}, v_{j}) = v_{i} \xrightarrow {e_{i_{1}}} v_{\cdot} \xrightarrow {e_{i_{2}}} ... \xrightarrow {e_{i_{k}}} v_{j} 的長度, 即 \displaystyle {d(v_{i}, v_{j}) = \left | P(v_{i}, v_{j}) \right | = e_{i_{1}} + e_{i_{2}} + ... + e_{i_{k}} = \sum \limits_{c = 1}^{k} e_{i_{c}}}. 對於無權圖來說, 任意邊的權重可以視為 1, 因此距離就是頂點數量減去一.

定義 10. 設有圖 \mathcal {G} = (V, E) 和 \mathcal {G}' = (V', E'), 如果 V' \subseteq V 且 E' \subseteq E, 那麼我們稱 \mathcal {G}' 是 \mathcal {G} 的子圖 (subgraph). 若 \mathcal {G}' 還滿足條件 c, 那麼我們稱 \mathcal {G}' 為生成子圖 (spanning subgraph).

定義 11. 若 \mathcal {G} 的生成子圖 \mathcal {G}' 滿足《【資料結構】樹》定義 1, 則稱 \mathcal {G}' 為 \mathcal {G} 的生成樹 (spanning tree). 若 \mathcal {G} 存在若干個互不相同的生成樹 \mathcal {T}_{1}, \mathcal {T}_{2}, ..., \mathcal {T}_{n}, 我們稱這些生成樹為 \mathcal {G} 的生成森林 (spanning forest). 記 s(\mathcal {T}) 是生成樹 \mathcal {T} 中邊的權重之和, 即若 \mathcal {T} 中有 m 條邊 e_{1}, e_{2}, ..., e_{m}, 對應的權重分別為 w_{1}, w_{2}, ..., w_{m}, 那麼有 \displaystyle {s(\mathcal {T}) = w_{1} + w_{2} + ... + w_{m} = \sum \limits_{i = 1}^{m}w_{i}}. 若生成森林中的 \mathcal {T}_{i} 滿足 \displaystyle {s(\mathcal {T}_{i}) = \min \left \{ s(\mathcal {T}_{1}), s(\mathcal {T}_{2}), ..., s(\mathcal {T}_{n}) \right \}}, 則稱 \mathcal {T}_{i} 為 \mathcal {G} 的最小生成樹 (minimal spanning tree).

定義 12. 如果圖 \mathcal {G} 中的頂點和邊的數量是有限的, 那麼我們稱 \mathcal {G} 為有限圖 (finite graph); 否則, 稱 \mathcal {G} 為無限圖 (infinite graph).

定義 13. 若圖 \mathcal {G} 中每一個節點的鄰居數量都相同, 為 k 個, 那麼我們稱 \mathcal {G} 為 k-正則圖 (k-regular graph, 簡稱為正則圖).

定義 14. 若圖 \mathcal {G} 中的頂點集合可以被劃分為 V_{1} 和 V_{2}. 對於 V_{1} 或者 V_{2} 中的任意兩個頂點 v_{i} 和 v_{j} (v_{i}, v_{j} \in V_{1} 或者 v_{i}, v_{j} \in V_{2}), 不存在 e \in E 使得 v_{i} 和 v_{j} 通過 e 相連接, 那麼我們稱 \mathcal {G} 為二部圖 (bipartite graph).

定義 15. 若圖 \mathcal {G} 兩個頂點 v_{i} 和 v_{j} 之間可以找到一條路徑使得從 v_{i} 出發可以到達 v_{j}, 那麼我們稱頂點 v_{i} 和 v_{j} 之間是連通的 (connected). 若 \mathcal {G} 是有向圖, 不僅存在一條 v_{i} 到 v_{j} 的路徑, 也存在一條 v_{j} 到 v_{i} 的路徑, 那麼我們稱頂點 v_{i} 和 v_{j} 之間是強連通的 (strongly connected); 但是如果僅存在一條 v_{i} 到 v_{j} 的路徑, 不存在一條 v_{j} 到 v_{i} 的路徑, 那麼我們稱頂點 v_{i} 和 v_{j} 之間是弱連通的 (weakly connected).

結合定義 15 和定義 9, 我們又可以給樹一個新的定義 : 沒有迴路的連通圖就是一棵樹.

定義 16. 若圖 \mathcal {G} 中任意兩個頂點 v_{i} 和 v_{j} 之間都是連通的, 那麼稱 \mathcal {G} 為連通圖 (connected graph). 若 \mathcal {G} 是有向圖, 且任意兩個頂點 v_{i} 和 v_{j} 之間都是強連通的, 那麼稱 \mathcal {G} 為強連通圖 (strongly connected graph).

若一個無向連通圖中有 n 個頂點, 那麼其必定至少有 n - 1 條非平行邊; 否則, 頂點就會被割裂成兩個不相通的部分. 對於有向圖來說, 若有 n 個頂點, 要使得有向圖連通, 其至少有 2(n - 1) 條非平行邊.

定義 17. 若圖 \mathcal {G} 的子圖 \mathcal {G}' 滿足

• \mathcal {G}' 是連通圖;
• 從 \mathcal {G}' 中任意移除一條邊, \mathcal {G}' 不再是連通圖,

那麼稱 \mathcal {G}' 是 \mathcal {G} 的極大連通子圖 (maximal connected subgraph), 又稱為連通元件 (connected component).

定義 18. 若有向圖 \mathcal {G} 的子圖 \mathcal {G}' 滿足

• \mathcal {G}' 是強連通圖;
• 從 \mathcal {G}' 中任意移除一條邊, \mathcal {G}' 不再是強連通圖,

那麼稱 \mathcal {G}' 是 \mathcal {G} 的極大強連通子圖 (maximal strongly connected subgraph), 又稱為強連通元件 (strongly connected component).

定義 19. 若頂點 v_{i} 連向了 k 個不同頂點, 那麼我們稱頂點 v_{i} 的度 (degree) 為 k, 記為 d(v_{i}) = k. 對於有向圖中的頂點 v_{i}, 若其連向了 m 個不同頂點, 有 n 個不同頂點連向了 v_{i}, 那麼我們稱 v_{i} 的出度 (out degree) 為 m, 入度 (in degree) 為 n, 分別記為 d_{\mathrm {out}}(v_{i}) = m, d_{\mathrm {in}}(v_{i}) = n.

當然, 無向圖中的邊也可以有出度和入度, 只不過對於無向圖來說, 邊的出度和入度都和邊的度相同.

除了上面提到的這些定義之外, 圖論中還有非常多其它定義. 因為這些定義不常用, 如果需要用到的話, 我們會在用到這些定義的文章中再進行介紹.

2. 性質

性質 1. 設 \mathcal {G} = (V, E) 是無向圖, 則有 \displaystyle {0 \leq \mathop {\mathrm {card}}{E} \leq \frac {\mathop {\mathrm {card}}{V}(\mathop {\mathrm {card}}{V} - 1)}{2}}.

證明 :

一個無向圖可以沒有任何邊, 即 E = \emptyset. 此時, \mathop {\mathrm {card}}{E} = 0. 另外, 無向圖中的每一個頂點都可以和剩餘 \mathop {\mathrm {card}}{V} - 1 個頂點相連接, 因此邊至多有 \mathop {\mathrm {card}}{V}(\mathop {\mathrm {card}}{V} - 1) 條. 但是兩個頂點之間相互連結的邊至需要有一條即可, 另外一條平行邊是重複的. 因此有 \displaystyle {0 \leq \mathop {\mathrm {card}}{E} \leq \frac {\mathop {\mathrm {card}}{V}(\mathop {\mathrm {card}}{V} - 1)}{2}}.

\blacksquare

定義 20. 若無向圖 \mathcal {G} = (V, E) 恰好有 \mathop {\mathrm {card}}{V}(\mathop {\mathrm {card}}{V} - 1) 條邊, 那麼我們稱 \mathcal {G} 為完全圖 (complete graph).

性質 2. 設 \mathcal {G} = (V, E) 是有向圖, 則有

1. 0 \leq \mathop {\mathrm {card}}{E} \leq \mathop {\mathrm {card}}{V}(\mathop {\mathrm {card}}{V} - 1);
2. \sum \limits_{i = 1}^{\mathop {\mathrm {card}}{V}}d_{\mathrm {in}}(v_{i}) = \sum \limits_{i = 1}^{\mathop {\mathrm {card}}{V}}d_{\mathrm {out}}(v_{i}) = \mathop {\mathrm {card}}{E}.

證明 :

在有向圖中, 兩個頂點之間至多有兩條非平行邊. 因此, 有向圖中邊的數量至多可以是對應無向圖的兩倍. 根據性質 1, 自然有 \displaystyle {0 \leq \mathop {\mathrm {card}}{E} \leq \mathop {\mathrm {card}}{V}(\mathop {\mathrm {card}}{V} - 1)}.

(1) \square

一個頂點的出度就是另外一個頂點的入度, 因此必然有 \displaystyle {\sum \limits_{i = 1}^{\mathop {\mathrm {card}}{V}}d_{\mathrm {in}}(v_{i}) = \sum \limits_{i = 1}^{\mathop {\mathrm {card}}{V}}d_{\mathrm {out}}(v_{i})}. \ \ \ \ \ \ \ \ \ \ (\mathrm {I}) 另外, 有向圖有多少條邊, 就對應了多少個出度, 自然有 \displaystyle {\sum \limits_{i = 1}^{\mathop {\mathrm {card}}{V}}d_{\mathrm {in}}(v_{i}) = \mathop {\mathrm {card}}{E}}. \ \ \ \ \ \ \ \ \ \ (\mathrm {II}) 結合 (\mathrm {I}) 式和 (\mathrm {II}) 式, 有 \displaystyle {\sum \limits_{i = 1}^{\mathop {\mathrm {card}}{V}}d_{\mathrm {in}}(v_{i}) = \sum \limits_{i = 1}^{\mathop {\mathrm {card}}{V}}d_{\mathrm {out}}(v_{i}) = \mathop {\mathrm {card}}{E}}.

(2) \square

\blacksquare

定理 1. 對於 n 個頂點, 都恰好存在一個 n 條邊的強連通圖. 其中, n > 1.

證明 :

我們可以將 n 個頂點散佈在一個圓的邊上, 隨意選擇一個頂點, 然後按照順時針或者逆時針方向, 不斷通過有向邊將當前頂點連接向下一個相鄰的頂點. 不難驗證, 我們得到了一個有向圖 \mathcal {G}. \mathcal {G} 中恰好有 n 個頂點和 n 條邊. 而從 \mathcal {G} 中任意一個頂點出發, 都可以到達其它頂點. 因此, \mathcal {G} 是一個強連通圖.

\blacksquare

定理 2. 設 \mathcal {G} 是無向圖, 那麼 \mathcal {G} 必定存在偶數個度為奇數的頂點.

證明 :

我們使用歸謬法進行證明. 不妨設存在奇數個度為奇數的頂點, 則這些頂點的度總和為奇數乘以奇數個, 最終結果必定也是奇數. 而度為偶數的頂點數量不論是奇數還是偶數, 這些頂點的度總和為奇數或者偶數乘以偶數, 最終結果必定是偶數. 那麼 \mathcal {G} 的度總和為奇數加上偶數, 結果必定是個奇數. 根據定義 19, 任何無向圖的度總和必定為偶數 (度為二, 任意數字和二相乘必定為偶數). 因此假設不成立, 從而\mathcal {G} 必定存在偶數個度為奇數的頂點.

\blacksquare

定理 3. 設 \mathcal {G} = (V, E) 是連通圖, 那麼 \mathcal {G} 必定包含一個度為 1 的頂點或者迴路, 又或者兩者都有. 其中, \mathop {\mathrm {card}}{V} > 1.

證明 :

像定理 1 的證明過程那樣, 把所有頂點散佈在圓的邊上, 並將相鄰的頂點進行連接. 不難驗證, 我們得到了一個 n 條邊的新圖 \mathcal {G}'. 由於 \mathcal {G}' 是極小連通圖, 所以 \mathcal {G}' 必定是 \mathcal {G} 的子圖 (更進一步地, 滿足連通條件的生成子圖).

現在任取頂點 v_{i}, 順時針或者逆時針走一圈便得到了一條迴路.

再任取兩個不同頂點 v_{i} 和 v_{j}, 移除連接著 v_{i} 和 v_{j} 的邊. 由於無向圖中的邊不具有方向性, 因此不論從 v_{i} 開始走還是從 v_{j} 開始走, 最終總能到達另一個頂點, 即 v_{i} 和 v_{j} 之間總是存在一條路徑. 此時, 頂點 v_{i} 或者 v_{j} 的度為 1.

接下來, 不論給 \mathcal {G}' 添加什麼樣的邊, 只要添加後的圖仍然是 \mathcal {G} 的子圖, 那麼就總存在一個度為 1 的頂點或者迴路, 又或者兩者都有.

\blacksquare

根據定理 3 及其證明過程, 我們可以得到兩個推論.

推論 1. 若存在 n 個頂點, 那麼必定存在一個恰好有 n - 1 條邊的無向連通圖. 其中, n > 1.

推論 2. 每一個具有 n 個頂點的無向連通圖至少有 n - 1 條邊.

定理 4. 設 \mathcal {G} = (V, E) 是至少包含一個迴路的無向連通圖, 邊 (v_{i}, v_{j}) \in E 至少出現在一個迴路中. 那麼圖 \mathcal {G}' = (V, E - \left \{ (v_{i}, v_{j}) \right \}) 仍然是一個連通圖.

證明 :

如果任意兩個頂點之間的路徑都可以不經過邊 (v_{i}, v_{j}), 那麼顯然 \mathcal {G}' 仍然是一個連通圖.

現在假設存在需要經過 (v_{i}, v_{j}) 的路徑. 由於 \mathcal {G} 是連通圖, 因此任意兩個不同頂點 u 和 v 之間總存在一條路徑 P(u, v). 設 x 是路徑 P(u, v) 中從 v_{i} 到 v_{j} 的次數, y 是路徑 P(u, v) 中從 v_{j} 到 v_{i} 的次數. 於是, P(u, v) 使用了邊 (v_{i}, v_{j}) 共計 x + y 次. 若 P(u, v) 沒有使用邊 (v_{i}, v_{j}), 那麼 x = y = 0.

由於邊 (v_{i}, v_{j}) 至少出現在一個迴路中, 不妨記這條迴路為 \displaystyle {P = v_{i} \leftrightarrow v_{j} \leftrightarrow v_{k_{1}} \leftrightarrow v_{k_{2}} \leftrightarrow ... \leftrightarrow v_{k_{c}} \leftrightarrow v_{i}}. 因為 \mathcal {G} 是無向圖, 因此 P 可以正向走也可以反向走. 於是我們又可以得到兩條相反的子路徑 \displaystyle {\overrightarrow {P} = v_{j} \rightarrow v_{k_{1}} \rightarrow v_{k_{2}} \rightarrow ... \rightarrow v_{k_{c}} \rightarrow v_{i}}, \displaystyle {\overleftarrow {P} = v_{i} \rightarrow v_{k_{c}} \rightarrow v_{k_{c - 1}} \rightarrow ... \rightarrow v_{k_{2}} \rightarrow v_{k_{1}} \rightarrow v_{j}}. 顯然, \overrightarrow {P} 是從 v_{j} 到 v_{i} 的路徑, \overleftarrow {P} 是從 v_{i} 到 v_{j} 的路徑.

現在, 從 \mathcal {G} 中移除邊 (v_{i}, v_{j}), 那麼任何路徑 P 中從 v_{i} 到 v_{j} 的部分就需要使用 \overleftarrow {P} 來置換, 共計置換 x 次; 從 v_{j} 到 v_{i} 的部分需要使用 \overrightarrow {P} 進行置換, 共計置換 y 次. 最終, 邊 (v_{i}, v_{j}) 並不影響 \mathcal {G} 的連通性.

綜上所述, \mathcal {G}' 仍然是連通圖.

\blacksquare

3. 空間佈局

除了完全二元樹 (《【資料結構】樹——二元樹》定義 3) 之外, 所有樹都是使用類似於前向連結串列 (《【資料結構】前向連結串列》) 或者連結串列 (《【資料結構】連結串列》) 的形式進行實作的. 圖也是類似, 最直觀的空間佈局就是類似於連結串列, 只是每一個頂點可能會有多個指向型標記 (《【資料結構】前向連結串列》定義 2). 不過, 圖還有另一種描述方式, 就是使用矩陣來描述.

我們給 Figure 6 中的賦權圖列一張表, 第 i 行第 j 列表示邊 \text {<} v_{i}, v_{j} \text {>} 的權 :

然後我們將表格簡化一下, 簡化為矩陣 \displaystyle {A = \begin {pmatrix} 0 & 2 & 0 & 0 & 0 \\ 0 & 0 & 5 & 0 & 0 \\ 0 & 8 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 10 \\ 0 & 9 & 3 & 4 & 0 \end {pmatrix}}. 其中, a_{ij} = \begin {cases} w(v_{i}, v_{j}) & {(v_{i}, v_{j}) \in E} \\ 0 & {(v_{i}, v_{j}) \notin E} \end {cases}, w(v_{i}, v_{j}) 是邊 (v_{i}, v_{j}) 的權重. 我們稱類似於 A 的矩陣為圖的鄰接矩陣 (adjacency matrix).

對於無權圖來說, 我們可以用 1 或者 0 來表示一條邊是否存在, 於是有 \displaystyle {a_{ij} = \begin {cases} 1 & {(v_{i}, v_{j}) \in E} \\ 0 & {(v_{i}, v_{j}) \notin E}. \end {cases}} 那麼 Figure 2 中的有向圖可以描述為 \displaystyle {\mathcal {G} = \begin {pmatrix} 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 \\ 0 & 1 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 1 \\ 0 & 1 & 1 & 1 & 0 \end {pmatrix}}.

由於無向圖中邊沒有方向, 因此無向圖的鄰接矩陣必定是一個對稱矩陣. 例如 Figure 1 中的無向圖的鄰接矩陣為 \displaystyle {\mathcal {G} = \begin {pmatrix} 0 & 1 & 1 & 1 & 0 \\ 1 & 0 & 0 & 1 & 1 \\ 1 & 0 & 0 & 0 & 1 \\ 1 & 1 & 0 & 0 & 0 \\ 0 & 1 & 1 & 0 & 0 \end {pmatrix}}. 由於矩陣 \mathcal {G} 的對稱性, 因此 \mathcal {G} 可以進一步被簡化為上三角矩陣或者下三角矩陣 : \displaystyle {\widehat {\mathcal {G}} = \begin {pmatrix} 0 & 1 & 1 & 1 & 0 \\ & 0 & 0 & 1 & 1 \\ & & 0 & 0 & 1 \\ & & & 0 & 0 \\ & & & & 0 \end {pmatrix}, \widecheck {\mathcal {G}} = \begin {pmatrix} 0 & & & & \\ 1 & 0 & & & \\ 1 & 0 & 0 & & \\ 1 & 1 & 0 & 0 & \\ 0 & 1 & 1 & 0 & 0 \end {pmatrix}}. 對於無向賦權圖, 我們只要將對應的 1 改為權重即可.

性質 3. 若圖 \mathcal {G} = (V, E, W) 中不存在自環, 那麼鄰接矩陣 \mathcal {G} = (a_{ij})_{\mathop {\mathrm {card}}{V} \times \mathop {\mathrm {card}}{V}} 滿足

1. a_{ii} = 0;
2. \sum \limits_{j = 1}^{\mathop {\mathrm {card}}{V}}a_{ij} = \sum \limits_{j = 1}^{\mathop {\mathrm {card}}{V}}a_{ji} = d(v_{i});
3. \sum \limits_{j = 1}^{\mathop {\mathrm {card}}{V}}a_{ij} = d_{\mathrm {out}}(v_{i});
4. \sum \limits_{j = 1}^{\mathop {\mathrm {card}}{V}}a_{ji} = d_{\mathrm {in}}(v_{i}).

這些性質都是由定義和性質 2 顯然可以得到的, 我們不再證明.

4. 尋訪

圖的尋訪是圖中最重要的操作, 很多和圖有關的問題都需要用到尋訪來解決. 樹的尋訪操作必定是從根節點開始的, 然後根據具體的尋訪步驟輸出也不太相同. 和樹的尋訪不同的是, 圖的尋訪並不規定要從哪一個頂點開始, 所以尋訪時可以隨機選擇一個頂點或者指定一個固定的頂點.

4.1 廣度優先搜尋法

廣度優先搜尋法 (breadth-first search) 有點像多管齊下, 各個可能到達的頂點都會去嘗試一下, 它需要借助佇列 (《【資料結構】佇列》) 來完成. 當遇到一個節點之後, 就會搜尋該節點的所有鄰居. 等所有鄰居都被找到之後, 把它們放入佇列中. 然後再從佇列頭部選擇頂點, 繼續對這個頂點進行廣度優先搜尋.

廣度優先搜尋法使用了和頂點數量相關的輔助空間. 首先, 佇列中至多有 O(v) 個頂點. 然後我們有需要使用 v 個大小的陣列來標記哪一些頂點已經尋訪過了, 哪一些頂點還沒有被尋訪. 因此, 廣度優先搜尋法的空間複雜度應該是 \Theta(v). 由於廣度優先搜尋法會尋訪所有頂點, 所以這裡需要 \Theta(v) 的時間複雜度. 另外, 廣度優先搜尋法還需要確定所有鄰居哪一些還沒有被尋訪, 所以會嘗試走過所有邊, 這裡需要 \Theta(e) 的時間複雜度. 最終, 廣度優先搜尋法的時間複雜度為 \Theta(v + e). 其中, v 是頂點數量, e 是邊的數量.

4.2 深度優先搜尋法

深度優先搜尋法 (depth-first search) 恰好和廣度優先搜尋法相反, 它有點像不到南牆不回頭. 深度優先搜尋法需要借助堆疊 (《【資料結構】堆疊》) 來完成. 從一個頂點開始, 深度優先搜尋會不斷往這個頂點未被尋訪的鄰居那邊前進, 直到遇到某個頂點的鄰居全部被尋訪過才停下來, 路途中的所有頂點都會被加入堆疊中. 當遇到某個頂點的鄰居都被尋訪過時, 將這個頂點從堆疊中移除, 然後從堆疊頂部再取一個頂點進行進行深度優先搜尋.

深度優先搜尋法的時間複雜度和空間複雜度和廣度優先搜尋法的分析過程是一樣的. 因此, 深度優先搜尋法的時間複雜度為 \Theta(v + e), 空間複雜度為 \Theta(v). 其中, v 是頂點數量, e 是邊的數量.

4.3 尋訪可解的經典問題

圖中的絕大多數問題都可以通過廣度優先搜尋法和深度優先搜尋法來解決. 在本節中我們只提一些非常經典的問題. 在第 5 節中, 我們將提出一些更加複雜的問題.

4.3.1 頂點可達性

頂點可達性問題是指給定圖中任意兩個頂點 v_{i} 和 v_{j}, 從 v_{i} 出發, 要求判斷是否可以到達 v_{j}. 顯然, 不論是廣度優先搜尋法還是深度優先搜尋法都可以解決這個問題. 但是仔細分析之後, 我們會發現廣度優先搜尋法使用的時間可能比深度優先搜尋法要少一些. 因為廣度優先搜尋法會一次性尋訪所有可到達的鄰居, 如果 v_{j} 恰好在這個範圍內, 我們可以立即終止搜尋. 對於深度優先搜尋法來說, 如果沒遇到 v_{j}, 或者 v_{j} 根本不在這條路上, 深度優先搜尋法並不會停止前進.

4.3.2 路徑存在性

路徑存在性問題是指給定圖中任意兩個頂點 v_{i} 和 v_{j}, 要求給出一條從 v_{i} 出發到 v_{j} 的路徑. 這個問題和頂點可達性問題最大的區別就是頂點可達性問題不要求記錄路徑. 此時, 深度優先搜尋的優勢就體現出來了. 從頂點 v_{i} 出發, 一旦遇到了 v_{j}, 堆疊中儲存的便是從 v_{i} 到 v_{j} 的路徑. 但是由於堆疊每次只能取出頂部或者尾部元素, 所以當把頂點從堆疊中全部取出來之後, 我們還需要對所有頂點進行反向排列才能得到從 v_{i} 到 v_{j} 的路徑; 否則, 這是一條潛在的從 v_{j} 到 v_{i} 的路徑 (畢竟並不是每一個圖都為無向圖). 為了避免堆疊這樣的問題, 我們可以將 Algorithm 2 中的堆疊更換為雙向佇列 (《【資料結構】雙向佇列 (雙端佇列)》).

4.3.3 連通性判定

對於一個圖來說, 如果它是連通的 (不論是強連通的還是弱連通的), 對這個圖進行一次廣度優先搜尋或者深度優先搜尋便可以尋訪所有頂點. 但是對於非連通的圖來說, 尋訪需要進行多次. 對於一個無向圖 \mathcal {G} 來說, 如果廣度優先搜尋或者深度優先搜尋需要進行 k 次才能將圖的頂點全部尋訪完畢, 那麼 \mathcal {G} 就有 k 個連通子圖. 要區分這些連通子圖, 我們可以用額外的輔助空間對這些頂點進行標記. 當進行第一次尋訪的時候, 把尋訪到的所有頂點標記為 1; 進行第二次尋訪的時候, 把尋訪到的所有頂點標記為 2; ...; 進行第 k 次尋訪的時候, 把尋訪到的所有頂點標記為 k. 那麼最終, k 個連通子圖將被標記區分開來.

4.3.4 迴路的判定

要判斷一個圖中是否存在迴路, 可以從任意頂點 v_{i} 出發進行深度優先搜尋, 如果最終可以回到 v_{i}, 就說明目前走過的這條路是迴路, 即圖中存在迴路. 若圖中有 n 個頂點, 而對這 n 個頂點進行深度優先搜尋之後, 沒有找到一條可以回到起點的路徑, 那麼這個圖中就不存在迴路.

4.3.5 生成樹

任意給定一個圖 \mathcal {G}, 要產生 \mathcal {G} 的生成樹, 我們既可以使用廣度優先搜尋法也可以用深度優先搜尋法. 因為在搜尋的時候, 我們會記錄哪一些頂點被尋訪過, 而被尋訪過的頂點是不會被再次尋訪的, 這就為產生一棵樹提供了實質性的幫助. 如果那些尋訪過的頂點再次被尋訪, 這就可能導致兄弟節點之間存在連接, 從而不再是一棵樹. 由於一個圖的生成樹有多個, 因此不同的尋訪方式也會產生不同的生成樹. 廣度優先搜尋法生成的樹是偏向於寬而短的, 深度優先搜尋法生成的樹是偏向於窄而長的, 這個顯然可以從這兩個搜尋方法的特點得到.

4.3.6 二部圖判定

仔細觀察 Figure 9, 我們會發現二部圖有點像數學中的影射 :

受到啟發, 我們可以用兩個集合來判斷一個圖是否為二部圖. 由 Figure 12 可以知道, 如果把圖分成兩個部分, 那麼一個集合中的頂點連接著的另一個頂點必定在另外一個集合中. 利用這個特性, 我們可以進行交替判定. 任意取圖中的一個頂點 v, 標記為已尋訪後把它放入集合中, 然後把它的鄰居標記為已尋訪後放入另外一個集合中, 同時再把這些鄰居放入佇列中. 那麼 v 的鄰居所連接著的頂點應該和 v 處於同一個集合中. 接著從佇列中不斷取頂點進行類似的判定, 如果遇到某個頂點連接著處於同一集合中的頂點, 那麼就可以判定這個圖不是二部圖. 如果所有頂點都被尋訪過了, 並且所有頂點都符合鄰居不和自己處於同一個集合中, 那麼就可以判定圖為二部圖.

5. 和圖有關的演算法

圖中存在著不少著名的演算法, 當然也包含不少臭名昭著的 NP 問題. 本節中我們將介紹一些經典的演算法.

5.1 拓撲排序

定義 21. 將有向圖 \mathcal {G} = (V, E) 的所有頂點按照某種順序排列在一條直線上形成一個序列 \mathcal {L}. 任取直線上兩個頂點 v_{i} 和 v_{j}, 不妨設 v_{i} 位於 v_{j} 之前. 若 \mathcal {L} 滿足對於頂點 v_{i} 和 v_{j}, 都有 \text {<} v_{j}, v_{i} \text {>} \notin E, 那麼稱 \mathcal {G} 排列得到的序列 \mathcal {L} 為拓撲序列 (topological sequence). 產生拓撲序列的過程稱為拓撲排序 (topological sorting).

顯然, 一個有向圖的拓撲序列並不唯一. 例如 Figure 13 中, 由於頂點 v_{1} 和 v_{2} 之間沒有連線, 所以我們可以交換這兩個頂點得到另一個拓撲序列.

拓撲序列一般用於描述任務的步驟, 有一些後期任務需要前期任務的鋪墊, 必須完成這些前期任務才能執行後期的任務, 特別是課程安排和任務調度. 拓撲序列還可以表示好友之間的關係, 特別是單向好友 (例如社交網站上的關注功能).

尋找圖的拓撲序列可以用貪婪演算法 (《貪婪演算法》) 來解決. 設函數 L = L(V) 可以產生含有所有頂點的一個序列, 那麼 L 就是目標函數. 任何由 L 產生且滿足拓撲序列定義的序列都是可行解. 如果沒有額外的條件, 這些可行解同時又是最佳解. 我們指定貪婪準則 : 每次從未加入序列的頂點中選擇一個頂點 u 加入序列最後一個位置, 要求加入的頂點滿足對於除 u 之外剩餘未加入序列的任意頂點 v, 不存在邊 \text {<} v, u \text {>}.

例題 1. 根據 Algorithm 3, 產生圖 \mathcal {G} 的拓撲序列.

證明 :

根據貪婪準則, 加入序列的頂點必須滿足入度為零. 於是, v_{1} 和 v_{2} 都滿足條件. 不妨我們先將 v_{2} 加入序列, 那麼從 \mathcal {G} 中移除 v_{2}.

接著, \mathcal {G} 中滿足入度為零的頂點有 v_{1} 和 v_{5}. 我們加入 v_{1}.

目前 \mathcal {G} 中滿足入度為零的頂點有 v_{3} 和 v_{5}, 我們加入 v_{5}.

現在 \mathcal {G} 中只剩下 v_{3} 滿足入度為零, 因此將 v_{3} 加入序列.

依次將頂點 v_{4} 和 v_{6} 加入序列.

最終將邊還原後, 我們就得到了一個拓撲序列.

\blacksquare

從例題 1 中, 我們可以得到, 一個圖的拓撲序列並不一定只有一個.

使用貪婪演算法解決問題我們必須證明兩個必要的條件 :

1. 當演算法成功, 那麼產生的序列及其邊形成的圖 \mathcal {L} 必定是一個拓撲序列;
2. 當演算法失敗, 那麼圖不存在拓撲序列.

對於第一條是顯然的, 因為貪婪準則已經要求產生的序列 \mathcal {L} 滿足拓撲序列的定義. 如果演算法成功產生一個序列, 那麼這個序列必定是拓撲序列.

引理 1. 若 Algorithm 3 失敗, 即 Algorithm 3 回傳空的序列, 那麼有向圖 \mathcal {G} = (V, E) 中存在迴路.

證明 :

當 Algorithm 3 失敗時, 必定存在一個頂點 v_{0} 無法加入序列, 其入度不為零. 那麼在未加入序列的頂點中, 就必定存在另一個頂點 v_{1} 滿足 \text {<} v_{1}, v_{0} \text {>} \in E. 若 \text {<} v_{0}, v_{1} \text {>} \in E, 那麼就找到了一條迴路. 若 v_{1} 可以被加入序列, 則必定另外存在一個未被加入序列的頂點 v_{1}' 滿足\text {<} v_{1}', v_{0} \text {>} \in E. 現在假設 v_{1} 也不能加入序列, 那麼必定又能找到一個未加入序列的頂點 v_{2} 滿足 \text {<} v_{2}, v_{1} \text {>} \in E. 由於 \mathcal {G} 為有限圖 (無限圖不存在拓撲序列), 如此反覆, 總能夠找到一條迴路.

\blacksquare

結合引理 1 和 Figure 13, 我們可以發現如果有向圖中存在迴路, 序列中至少有一條邊的方向和其它邊相反. 因此我們可以斷言 : 當 Algorithm 3 失敗, 那麼給定的有向圖不存在拓撲序列.

由貪婪演算法驅動的 Algorithm 3 需要的輔助空間和頂點數量有關, 和邊的數量無關, 因為需要額外空間儲存拓撲序列的頂點. 因此拓撲排序的空間複雜度為 \Theta(v). 當第一個頂點被加入序列時, 需要檢查剩下 v - 1 個頂點是否存在向第一個頂點連接的有向邊, 因此需要檢查 v - 1次; 對於第二個頂點需要檢查 v - 2 次; ...; 對於第 v - 2 個頂點需要檢查一次; 最後一個頂點直接加入, 不需要檢查. 那麼共計需要檢查 \displaystyle {(v - 1) + (v - 2) + ... + \big ( v - (v - 1) \big ) + (v - v) = \sum \limits_{i = 1}^{v} v - i = \frac {v^{2} - v}{2}}. 根據《漸近分析基礎》中的定義 3, 即 Θ 記法的定義, 拓撲排序的時間複雜度為 \Theta(v^{2}). 當頂點數量非常多的時候而邊的數量比較少的時候, 我們可以將 Algorithm 3 中對頂點的檢查改為對邊的檢查, 即檢查所有邊中是否存在 \text {<} v', v \text {>}. 此時, 拓撲排序的時間複雜度為 \Theta(v + ve). 但是如果圖是以鄰接矩陣儲存的話, 我們就不需要尋訪和當前頂點無關的邊, 此時時間複雜度進一步降低為 \Theta(v + e). 其中, v 是頂點數量, e 是邊的數量.

5.2 二部圖的最小覆蓋

二部圖的頂點可以被分成兩個集合 A 和 B. 若 A 的某個子集 A' 滿足 B 中任意一個頂點至少與 A' 中一個頂點相連接, 那麼我們說 A' 覆蓋 (cover) 了 B, 又稱 A' 是 B 的一個覆蓋. 若 A' 中不存在 B 的更小覆蓋時, 那麼我們說 A' 是 B 的最小覆蓋 (minimal cover).

在二部圖中尋找最小覆蓋類似於在集合的覆蓋問題. 給出 n 個集合 \mathscr {S} = \left \{ S_{1}, S_{2}, ..., S_{n} \right \}, 每個集合中的元素來自全域集合 U. 若存在 k 個集合使得 \displaystyle {S_{i_{1}} + S_{i_{2}} + ... + S_{i_{k}} = U}, 那麼稱 \mathscr {S}' = \left \{ S_{i_{1}}, S_{i_{2}}, ..., S_{i_{k}} \right \} 為 \mathscr {S} 的一個覆蓋. 若從 \mathscr {S}' 中移除任意一個集合, 那麼 \mathscr {S}' 將不再是 \mathscr {S} 的覆蓋, 那麼稱 \mathscr {S}' 為 \mathscr {S} 的最小覆蓋. 其中, k \leq n, i_{j} = 1, 2, ..., n (j = 1, 2, ..., k). 二部圖中尋找最小覆蓋和集合的最小覆蓋問題是可以相互轉換的.

集合覆蓋問題是一個 NP 問題, 其決定性問題 (給定 n 個集合和一個全域集合, 是否存在 k (k \leq n) 個集合之並的結果為全域集合) 是一個 NP 完備問題.

在《貪婪演算法》第 4 節中我們介紹過, 貪婪演算法可以快速獲得 NP 問題的近似解. 對於二部圖的最小覆蓋問題或者集合的最小覆蓋問題, 我們可以通過貪婪演算法來尋找解. 一個可能的快速啟發式演算法是不斷從剩餘頂點中挑選一個頂點加入覆蓋 A', 挑選的準則是該頂點最大化地覆蓋了 B 中還沒有覆蓋的那一部分. 例如頂點 v_{1} 覆蓋了 B 中六個頂點, 但是這六個頂點中有五個頂點被已經加入 A' 中的頂點覆蓋過了, 而 v_{2} 覆蓋了 B 中三個頂點, 但是這三個頂點都沒有被 A' 中的頂點覆蓋過. 此時, 如果找不到覆蓋率比 v_{2} 高的頂點, 那麼就將 v_{2} 加入 A'. 由於這個方法是啟發式演算法, 所以它只能保證可能能夠找到最小覆蓋, 並不保證 A' 一定是最小覆蓋.

對於上面的啟發式演算法, 每次從 A 中選取頂點加入 A' 之後, 都需要更新 A 中剩餘頂點和 B 中未覆蓋頂點的連接數量. 我們每次從 A 中選取頂點的依據就是連接數量哪一個最多. 那麼比較適合解決這個問題的資料結構就是贏者樹 (《【資料結構】樹——贏者樹》).

斷言 1. 若二部圖中不存在覆蓋, 上述啟發式演算法必定找不到覆蓋. 此時, 二部圖中存在多個連通子圖.

證明 :

設二部圖 \mathcal {G} = (V, E) 的頂點可以被分為 A 和 B, 我們要在 A 中尋找 B 的覆蓋 A'. 對於 A 中任意兩個頂點 a 和 b 以及 B 中任意兩個頂點 c 和 d, 必定有 (a, b) \notin E 且 (c, d) \notin E; 否則, \mathcal {G} 不再是二部圖. 當 a 和 b 與集合 B 中的任意頂點都不存在邊, c 和 d 與集合 A 中的任意頂點都不存在邊, 那麼二部圖分劃分有誤.

現在考慮 A' = A, 若 A' 不是 B 的覆蓋, 那麼 B 中必定存在一個獨立的頂點 v, 對於任意 v_{i} \in V, 必定有 (v, v_{i}) \notin E 且 (v_{i}, v) \notin E. 這個時候, 二部圖就存在至少兩個連通子圖.

\blacksquare

5.3 最小生成樹

對於加權無向連通圖 G = (V, E, W), 我們希望產生 \mathcal {G} 的一棵生成樹 \mathcal {T}, 其中 \mathcal {T} 滿足所有邊的權重之和是生成樹中最小的. 解決這個問題一共有三個經典的演算法 : Kruskal 演算法, Prim 演算法和 Borůvka 演算法 (也稱為 Sollin 演算法). 這三個經典的演算法都是以貪婪演算法為基礎的.

對於生成樹, 我們可以斷定的是一共有 \mathop {\mathrm {card}}{V} 個節點, 有 \mathop {\mathrm {card}}{V} - 1 條邊.

Kruskal 演算法是分步驟從 E 中選擇 n - 1 條邊, 選擇邊的貪婪準則是從剩餘邊中選擇一條權重最小且不會產生迴路的邊.

很明顯, Kruskal 演算法的空間複雜度為 \Theta(v) + O(e), 因為需要儲存生成樹的節點和邊. 而時間複雜度取決於迴路的檢測. 由於 v 個頂點至多有 v - 1 條邊, 如果不計給邊排序所耗費的時間, 那麼此處的時間複雜度為 \Theta(v). 另外, 當加入一條邊也就意味著有一個新的頂點加入, 那麼這個新的頂點就要和已經加入的所有頂點進行迴路檢測, 這裡的時間複雜度為 \Theta(v^{2}). 因此, Kruskal 演算法的時間複雜度為 \Theta(v^{2}). 如果算上給邊排序的時間, 那麼 Kruskal 演算法的時間複雜度為 \Theta(e\log {e} + v^{2}). 其中, v 是頂點數量, e 是邊的數量.

Tip : 使用併查集 (《【資料結構】並查集》) 可以將時間複雜度降到 O(e\log {v}) = O(e\log {e}).

斷言 2. 若無向圖 \mathcal {G} = (V, E, W) 存在生成樹, 那麼 Kruskal 演算法產生的樹必定是 \mathcal {G} 的最小生成樹.

證明 :

我們用歸納法進行證明.

當 \mathop {\mathrm {card}}{V} = 1 時, Kruskal 演算法無需運作, \mathcal {G} 本身既是樹也是圖, 自然 \mathcal {G} 就是自身的最小生成樹.

當 \mathop {\mathrm {card}}{V} = 1 且 \mathop {\mathrm {card}}{E} = 1 時, Kruskal 演算法產生的生成樹就是 \mathcal {G}, 此時 \mathcal {G} 也是自身的最小生成樹.

不妨設 \mathop {\mathrm {card}}{V} \leq k 時, Kruskal 演算法產生的生成樹都是最小生成樹.

當 \mathop {\mathrm {card}}{V} = k + 1 時, 設 \mathcal {T}_{k + 1} = (V_{k + 1}, E_{k + 1}) 是由 Kruskal 演算法產生的生成樹, \mathcal {T}_{k} = (V_{k}, E_{k}) 是 Kruskal 演算法當 \mathop {\mathrm {card}}{V} = k 時所產生的最小生成樹, E_{k + 1} = E_{k} \cup \left \{ (v_{i}, v_{j}) \right \}. 現在假設存在一棵權重和更小的樹 \mathcal {U} = (V', E') 滿足 \displaystyle {\sum \limits_{i = 1}^{\mathop {\mathrm {card}}{V' - 1}}w(v_{i}, v_{i + 1}) < \sum \limits_{i = 1}^{\mathop {\mathrm {card}}{V_{k + 1} - 1}}w(v_{i}, v_{j}). \ \ \ \ \ \ \ \ \ \ (\mathrm {III})} 其中, V' \subset V 且 E' \subset E, w(v_{i}, v_{j}) 是邊 (v_{i}, v_{j}) 的權重. 設 v 是當 \mathop {\mathrm {card}}{V} = k + 1 時新加入的頂點, 即 V_{k + 1} = V_{k} \cup \left \{ v \right \}. 由於 \mathcal {U} \neq \mathcal {T}_{k + 1}, 那麼存在一條邊 (i, v) 滿足 (i, v) \in V_{k + 1} 但 (i, v) \notin V'; 也存在另一條邊 (j, v) 滿足 (j, v) \in V' 但 (j, v) \notin V_{k + 1}. 根據 Kruskal 演算法的選擇準則, 其選擇的是權重最小且不構成迴路的邊, 因此即使 \mathcal {U} 的權重和比 \mathcal {T}_{k + 1} 更小, 但是在選擇從其它頂點到 v 的邊中, Kruskal 演算法選擇的邊應該具有更小的權重, 也就是說至少有 \displaystyle {w(i, v) \leq w(j, v)}. 又因為 E_{k} = E_{k + 1} \backslash \left \{ (i, v) \right \} = E' \backslash \left \{ (j, v) \right \}, 故有 \displaystyle {\sum \limits_{i = 1}^{\mathop {\mathrm {card}}{V_{k}} - 1}w(v_{i}, v_{i + 1}) + w(i, v) \leq \sum \limits_{i = 1}^{\mathop {\mathrm {card}}{V_{k}} - 1}w(v_{i}, v_{i + 1}) + w(j, v)}. 若且唯若 w(i, v) = w(j, v) 時, 等號才成立. 如果等號成立, 那麼假設不成立. 因為等號的成立就意味著兩種可能, 就是 i = j 或者 Kruskal 演算法存在多條可選擇且權重相同的邊. 若 i = j, 必定有 \mathcal {T}_{k + 1} = \mathcal {U}, 於是 \mathcal {U} 的權重和不可能比 \mathcal {T}_{k + 1} 小; 若 Kruskal 演算法存在多條可選擇且權重相同的邊, 雖然 \mathcal {U} \neq \mathcal {T}_{k + 1} 可能成立, 但是 \mathcal {U} 的權重和也不可能比 \mathcal {T}_{k + 1} 小. 當 w(i, v) \neq w(j, v) 時, 即 w(i, v) < w(j, v) 時, 有 \displaystyle {\begin {aligned} &\sum \limits_{i = 1}^{\mathop {\mathrm {card}}{\mathcal {T}_{k}} - 1}w(v_{i}, v_{i + 1}) + w(i, v) < \sum \limits_{i = 1}^{\mathop {\mathrm {card}}{\mathcal {T}_{k}} - 1}w(v_{i}, v_{i + 1}) + w(j, v) \\ &\Rightarrow \sum \limits_{i = 1}^{\mathop {\mathrm {card}}{\mathcal {T}_{k + 1}} - 1}w(v_{i}, v_{i + 1}) < \sum \limits_{i = 1}^{\mathop {\mathrm {card}}{\mathcal {U}} - 1}w(v_{i}, v_{i + 1}), \end {aligned}} 這和 (\mathrm {III}) 式相矛盾. 因此, 當 w(i, v) < w(j, v) 時, 假設同樣不能成立. 最終, 當 \mathop {\mathrm {card}}{V} = k + 1 時, 由 Kruskal 演算法產生的生成樹 \mathcal {T}_{k + 1} 就是最小生成樹.

綜上所述, 若無向圖 \mathcal {G} = (V, E, W) 存在生成樹, 那麼 Kruskal 演算法產生的樹必定是 \mathcal {G} 的最小生成樹.

\blacksquare

Prim 演算法的選擇準則是基於頂點的, 過程就像是一棵不斷生長的樹. 首先任意從 V 中選取一個頂點加入 V'. 對於任意 u \in V', 我們需要找到權重最小的邊 (u, v), 其中 v \notin V'. 接著我們把 v 加入 V'. 不斷重複這個步驟直到 \mathop {\mathrm {card}}{V} = \mathop {\mathrm {card}}{V'} 為止. 由於每次加入的頂點都是新的頂點, 所以必然不會形成迴路. 如果圖採用鄰接矩陣來實作, 那麼 Prim 演算法的空間複雜度為 \Theta(1), 時間複雜度為 \Theta(v^{2}). 空間複雜度和 Kruskal 一樣, 是 \Theta(v) + O(e). 其中, v 是頂點數量, e 是邊的數量.

斷言 3. 若無向圖 \mathcal {G} = (V, E, W) 存在生成樹, 那麼 Prim 演算法產生的樹必定是 \mathcal {G} 的最小生成樹.

這個斷言的證明過程和斷言 2 是一樣的, 此處我們不再證明.

Borůvka 演算法結合了 Kruskal 演算法和 Prim 演算法, 在每一步選擇若干條邊. 一開始, 所有頂點都是一個獨立的樹, 所有頂點形成一個森林, 所有邊都是候選邊. 對於森林中獨立的樹, 尋找樹中所有頂點擁有的權重最小的候選邊 (類似於 Prim 演算法). 如果候選邊能夠將兩棵樹連接起來形成一棵樹, 那麼就將候選邊從候選集合中移除, 加入到樹中 (類似於 Kruskal 演算法). 將兩棵樹連接起來必定不會產生迴路, 所以當森林中只有一棵樹的時候, 那麼最終這棵樹就是由 Borůvka 演算法產生的最小生成樹.

Borůvka 演算法需要進行 \log_{2}{v} 次合併, 每次合併兩棵樹, 最終才能將獨立的頂點合併成一棵樹. 這裡的時間複雜度為 \Theta(\log {v}). 由於每次都需要從候選邊中選擇權重較小的, 所以共計有 \Theta(e\log {v}) 次選擇. 於是我們可以得到 Borůvka 演算法的時間複雜度為 \Theta(e\log {v}). 而 Borůvka 演算法所需要的額外輔助空間和 Kruskal 演算法與 Prim 演算法類似, 因此空間複雜度為 \Theta(v) + O(e). 其中, v 是頂點數量, e 是邊的數量.

斷言 4. 若無向圖 \mathcal {G} = (V, E, W) 存在生成樹, 那麼 Borůvka 演算法產生的樹必定是 \mathcal {G} 的最小生成樹.

這個斷言的證明過程和斷言 2 是一樣的, 此處我們不再證明.

根據前人的實驗經驗, 一般情況下, Prim 演算法是三個演算法中效能最高的.

5.5 最短路徑

在圖中尋找最短路徑問題非常重要, 有著非常多的應用. 比如在運送貨物的過程中, 我們通常選擇距離最短的線路. 這個時候, 頂點便是目的地, 邊的權重是兩個地方之間的距離. 在路由器的封包轉遞過程中, 為了儘快到達目的路由器, 避免封包中的資料丟失, 我們也會選擇儘量短的線路. 此時, 頂點是路由器, 邊的權重是兩個路由器之間傳遞資料的時間. 在旅行中, 不同地方之間的機票價格通常也不太相同, 我們都希望選擇花費最少的旅遊路線. 此時, 頂點便是旅行目的地, 邊是兩個地方之間的機票價格.

5.5.1 起點確定的最短路徑

給定加權連通圖 \mathcal {G} = (V, E, W), 從任意一個頂點出發到其它頂點的路徑可能存在多條, 一般來說我們都希望找到最短的路徑. 這個問題也可以用貪婪演算法來解決. 對於路徑 P(v_{0}, v_{n}) = v_{0} \rightarrow v_{1} \rightarrow v_{2} \rightarrow ... \rightarrow v_{n}, 目標函數為 \ell = \sum \limits_{i = 1}^{n}w(v_{i - 1}, v_{i}). 其中, w(v_{i}, v_{j}) 是邊 (v_{i}, v_{j}) 的權重. 只要 P(v_{0}, v_{n}) 是一條通路, 那麼就是可行解, 能夠使得目標函數 \ell 取得最小值的路徑為最佳解. 另外, 我們規定從頂點到自身的路徑長度 P(v_{0}, v_{0}) = 0.

我們並無法直接確定一條最短路徑, 為此我們要尋訪每一個可能的頂點, 得到起點到所有頂點的最短路徑. 設起點為 v_{0}, 目標頂點為 v_{n}. 若路徑 P(v_{0}, v_{n}) 是最短路徑, 那麼任意子路徑 P(v_{i}, v_{j}) 也是最短路徑; 否則 P(v_{0}, v_{n}) 必定不是最短的, 還有優化的空間. 其中, i, j = 0, 1, ..., n 且 i \neq j.

我們建立三個影射 M = M(v_{i}), L = L(v_{i}) 和 R = R(v_{i}). 其中, i = 1, 2, ..., n. 其中, 影射 M 表示從起點 v_{0} 到 v_{i} 的最短路徑長度; 影射 L 表示從起點 v_{0} 到 v_{i} 經過的最後一個頂點 (根據上面的表述, 我們一般有 L(v_{i}) = v_{i - 1}, 為了避免路徑頂點中的注標和前面章節敘述衝突, 所以此處採用了 L(v_{i}) 表示. 但是對於路徑 v_{0} \rightarrow v_{3} \rightarrow v_{6}, 那麼 L(v_{6}) = v_{3} \neq v_{5}); 影射 R 用於記錄頂點 v_{i} 是否已經被尋訪 (為了確定 v_{i + 1}, 我們必須尋訪 v_{1} 可能到達的所有鄰居). 初始時, M(v_{i}) = \infty, L(v_{i}) = \infty, R(v_{i}) = 0.

現在我們可以設定貪婪準則 : 一開始取起點 v_{0}, 令 M(v_{0}) = 0, M(v_{i}) = +\infty, R(v_{0}) = 1. 接下來對於任意 R(v_{i}) = 1 , 選擇一條權重 w(v_{i}, v_{j}) 最小的邊. 若有 M(v_{i}) + w(v_{i}, v_{j}) < M(v_{j}), 那麼更新 M(v_{j}) = M(v_{i}) + w(v_{i}, v_{j}), L(v_{j}) = v_{i} 且 R(v_{j}) = 1. 其中, i, j = 1, 2, ..., n, i \neq j. 這裡要注意, 如果 M(v_{i}) 更新且存在路徑需要經過 v_{i}, 那麼排在 v_{i} 之後所有頂點的 M 值都要陪同更新. 若更新前有 M(v_{i}) = M_{0}, 更新後有 M(v_{i}) = M', 那麼排在 v_{i} 之後所有頂點的 M 值都要減去 M' - M_{0}. 換句話說, 當 v_{i} 不是最後被加入的頂點, 那麼才需要去更新.

根據貪婪準則, 當任意 R(v_{i}) = 1 時 (i = 0, 1, 2, ..., n), 那麼我們就得到了一條從指定起點 v_{0} 到任意其它頂點的最短路徑及其長度. 最短路徑由影射 L 產生, 長度由影射 M 記錄. 若指定頂點 v_{n} 為終站頂點, 由影射 L 得到從 v_{0} 到 v_{n} 的過程是 : 將 v_{n} 排列在最後一個; 然後將 L(v_{n}) 排列在 v_{n} 之前; 將 L(L(v_{n})) 排列在 L(v_{n}) 之前; ...; 直到 L(L(...L(v_{n})...)) = v_{0} 為止, 將 v_{0} 排列在首個位置, 最終得到一條從 v_{0} 到 v_{n} 的最短路徑. 我們稱這個方法為 Dijkstra 演算法.

斷言 5. 對任意加權圖 \mathcal {G} = (V, E, W), 使用 Dijkstra 演算法得到的起點到任意其它頂點的路徑必定是最短路徑.

證明 :

我們使用歸納法進行證明. 要證明斷言成立, 即要證明每一步得到的路徑都是最短的. 我們用 n 表示演算法進行到第 n 步. 其中, n \leq \mathop {\mathrm {card}}{V}.

當 n = 1 時, 演算法剛剛開始, 只有 v_{0} 被尋訪, 因此路徑中只有一個頂點, 這條路徑必然是最短路徑.

不妨設 n \leq k 時, Dijkstra 演算法產生的都是最短路徑.

當 n = k + 1 時, 記 P_{k} 為 Dijkstra 演算法當 n = k 時產生的從 v_{0} 到某一頂點的路徑, P_{k + 1} 為Dijkstra 演算法當 n = k + 1 時產生的從 v_{0} 到某一頂點的路徑. 若當 n = k + 1 時, 被尋訪的頂點為 v, 那麼顯然有 P_{k + 1} = P_{k} \rightarrow v. 現在我們要證明 P_{k} 為最短路徑. 不妨設存在一條起點 v_{0} 到 v 的最短路徑為 P (P \neq P_{k + 1}), 且 \displaystyle {\sum \limits_{i = 1}^{\mathop {\mathrm {card}}{P}}w(v_{i - 1}, v_{i}) < \sum \limits_{i = 1}^{\mathop {\mathrm {card}}{P_{k + 1}}}w(v_{i - 1}, v_{i})}. 由於 P_{k} 是當 n = k 時產生的最短路徑, 所以 P 中存在一個頂點 x, 從這個頂點開始, P 中的路徑相比較於 P_{k + 1} 中的路徑產生了偏離. 設 P_{x} 是 P 的子路徑, 且以 x 為終點, y 是路徑 P 中 x 的下一個頂點, z 是路徑 P_{k + 1} 中 x 的下一個頂點. 那麼有 \displaystyle {\sum \limits_{i = 1}^{\mathop {\mathrm {card}}{P_{x}}}w(v_{i - 1}, v_{i}) + w(x, y) \leq \sum \limits_{i = 1}^{\mathop {\mathrm {card}}{P_{x}}}w(v_{i - 1}, v_{i}) + w(x, z)}. 若等號成立, 那麼說明頂點 y 和 z 可以相互替換, 無論用哪一個替換另外一個, 必然導致偏移處 x 向後移動. 當 y 和 z 不再能相互替換, 此時等號不成立, 便有 \displaystyle {w(x, y) < w(x, z). \ \ \ \ \ \ \ \ \ \ (\mathrm {IV})} 根據 Dijkstra 演算法, 當 x 確定之後, z 的選擇必定需要滿足 w(x, z) 是未尋訪邊中權重最小的, 於是又有 w(x, z) < w(x, y), 這和 (\mathrm {IV}) 式矛盾, 因此 P 不存在. 最終, 由 Dijkstra 演算法產生的 P_{k + 1} 就是最短路徑.

綜上所述, 對任意加權圖 \mathcal {G} = (V, E, W), 使用 Dijkstra 演算法得到的起點到任意其它頂點的路徑必定是最短路徑.

\blacksquare

例題 2. 以 v_{5} 為起點, 根據 Dijkstra 演算法尋找從 v_{5} 到各其它頂點的最短路徑.

解 :

我們可以使用列表的方式來記錄影射 M, L 和 R 的更新.

	v_{5}	v_{1}	v_{2}	v_{3}	v_{4}
M(v_{i})	0	+\infty	+\infty	+\infty	+\infty
L(v_{i})	\infty	\infty	\infty	\infty	\infty
R(v_{i})	1	0	0	0	0

從 v_{5} 出發, 權重最小的邊是 (v_{5}, v_{3}). 根據貪婪準則, 我們更新 M(v_{3}) = M(v_{5}) + w(v_{5}, v_{3}) = 3, L(v_{3}) = v_{5} 和 R(v_{3}) = 1.

	v_{5}	v_{1}	v_{2}	v_{3}	v_{4}
M(v_{i})	0	+\infty	+\infty	3	+\infty
L(v_{i})	\infty	\infty	\infty	v_{5}	\infty
R(v_{i})	1	0	0	1	0

從 v_{5} 和 v_{3} 出發, 權重最小的邊是 (v_{3}, v_{4}). 因此更新 M(v_{4}) = M(v_{3}) + w(v_{3}, v_{4}) = 5, L(v_{3}) = v_{4} 和 R(v_{4}) = 1.

	v_{5}	v_{1}	v_{2}	v_{3}	v_{4}
M(v_{i})	0	+\infty	+\infty	3	5
L(v_{i})	\infty	\infty	\infty	v_{5}	v_{3}
R(v_{i})	1	0	0	1	1

從 v_{5}, v_{3} 和 v_{4} 出發, 權重最小的邊是 (v_{5}, v_{4}). 由於 M(v_{5}) + w(v_{5}, v_{4}) < M(v_{4}), 因此我們更新 M(v_{4}) = M(v_{5}) + w(v_{5}, v_{4}) = 4, L(v_{4}) = v_{5}. 又因為所有路徑中 v_{4} 之後暫時不存在頂點, 所以無需進行後續的更新.

	v_{5}	v_{1}	v_{2}	v_{3}	v_{4}
M(v_{i})	0	+\infty	+\infty	3	4
L(v_{i})	\infty	\infty	\infty	v_{5}	v_{5}
R(v_{i})	1	0	0	1	1

仍然從 v_{5}, v_{3} 和 v_{4} 出發, 權重最小的邊是 (v_{3}, v_{2}). 我們更新 M(v_{2}) = M(v_{3}) + w(v_{3}, v_{2}) = 11, L(v_{2}) = v_{3}, R(v_{2}) = 1.

	v_{5}	v_{1}	v_{2}	v_{3}	v_{4}
M(v_{i})	0	+\infty	11	3	4
L(v_{i})	\infty	\infty	v_{3}	v_{5}	v_{5}
R(v_{i})	1	0	1	1	1

從 v_{5}, v_{3}, v_{4} 和 v_{2} 出發, 權重最小的邊是 (v_{2}, v_{1}). 我們更新 M(v_{3}) = M(v_{5}) + w(v_{5}, v_{3}) = 3, L(v_{3}) = v_{5} 和 R(v_{3}) = 1.

	v_{5}	v_{1}	v_{2}	v_{3}	v_{4}
M(v_{i})	0	12	11	3	4
L(v_{i})	\infty	v_{2}	v_{3}	v_{5}	v_{5}
R(v_{i})	1	1	1	1	1

剩下的邊中權重最小的是 (v_{1}, v_{2}), 由於 M(v_{1}) + w(v_{1}, v_{2}) > M(v_{2}), 所以不進行更新. 對於邊 (v_{2}, v_{3}) 也是類似的處理. 接下來權重最小的邊為 (v_{5}, v_{2}), 因 M(v_{5}) + w(v_{5}, v_{2}) < M(v_{2}), 因此更新 M(v_{2}) = 9, L(v_{2}) = v_{5}. 此時, 排在 v_{2} 後面所有頂點的 M 值都需要更新, 減去當前更新的差值. 這裡只需要更新 v_{1}, 讓 M(v_{1}) 減去二, 即 M(v_{1}) = 10.

	v_{5}	v_{1}	v_{2}	v_{3}	v_{4}
M(v_{i})	0	10	9	3	4
L(v_{i})	\infty	v_{2}	v_{5}	v_{5}	v_{5}
R(v_{i})	1	1	1	1	1

還剩下一條 (v_{5}, v_{1}), 並不能滿足 M(v_{5}) + (v_{5}, v_{1}) < M(v_{1}) = 10. 最終, Dijkstra 演算法完成, 從 v_{5} 出發到各頂點的最短路徑都找到了.

\blacksquare

從例題 2 來看, 我們至少需要三倍頂點數量的輔助空間來儲存 M, L 和 R, 還需要邊數量的輔助空間來儲存邊是否被尋訪. 因此, Dijkstra 演算法的空間複雜度為 \Theta(v + e). 如果使用優先佇列 (《【資料結構與演算法】堆積, 堆積排序和優先佇列》) 作為底層資料結構, 那麼當接納一個新的頂點之後, 必須把頂點相關的所有邊放入優先佇列. 最終, 所有邊都會被放入優先佇列, 時間複雜度為 \Theta(e\log {e}). 最短路徑必定只有 v - 1 條邊會從優先佇列中被取出, 時間複雜度為 \Theta(v\log {e}). 最終, Dijkstra 演算法的時間複雜度為 \Theta \big ( (v + e)\log {e} \big ). 其中, v 是頂點數量, e 是邊的數量.

Dijkstra 演算法不僅僅可以解決起點確定的最短路徑問題, 還可以解決起點終站都確定的最短路徑問題. 對於終站頂點確定但是起點不確定的最短路徑問題 (主要是針對有向圖, 無向圖等價於起點確定), 我們只需要把所有邊反向之後應用 Dijkstra 演算法即可. 另外, 對於最長路徑, 將貪婪準則中的選擇權重最小改為權重最大就可以了. 如果圖不是連通的, 那麼我們可以分別對連通子圖應用 Dijkstra 演算法求最短路徑.

5.5.2 權重為負的最短路徑

一般來說, 圖是用來模擬實際問題的, 所以權重都是正的. 但是也存在一些權重為負的情況, 例如當使用圖計算投資回報的時候, 有一些邊的權重就可能為負值. 這個時候 Dijkstra 演算法是否還適用呢?

從 v_{1} 出發, 應用 Algorithm 7, 我們可以得到

由於 M(v_{4}) + w(v_{4}, v_{2}) = -3 < M(v_{2}) = 1, 因此我們更新 M(v_{2}) = -3, L(V_{2}) = v_{4}. 那麼有

現在還要做的是更新位於 v_{2} 之後頂點的 M 值. 但是我們透過 Figure 18-3 發現 v_{2} 之後沒有頂點了. 於是, Dijkstra 演算法結束. 但是實際上, 對於頂點 v_{3}, 還有一條更短的路徑 : v_{1} \rightarrow v_{4} \rightarrow v_{2} \rightarrow v_{3}. 就是因為 v_{3} 提前於 v_{2} 被尋訪, 所以導致這條路徑沒有被演算法發現.

斷言 6. 對任意加權圖 \mathcal {G} = (V, E, W), 若存在 w \in W 滿足 w < 0, 則 Dijkstra 演算法不保證找到的路徑就是最短路徑.

這個斷言可以根據上面範例輕鬆得到, 但是 Dijkstra 演算法仍然有機率找到正確的最短路徑.

要找到帶有負值的賦權圖中的最短路徑, 我們必須假設圖中不存在權重之和為負的迴路. 如果存在的話, 最短路徑是不存在的, 因為我們只需要不斷繞著這條迴路走就可以讓權重之和靠近不存在的負值 -\infty.

由於 Dijkstra 演算法是基於貪婪演算法的, 所以每一步決定作出之後是無法更改的, 這是導致 Dijkstra 演算法在帶有負值的賦權圖上可能失敗的根本原因. 因此, 我們只需要改變一下這個規則, 不再採用貪婪演算法, 而是每一步都嘗試動態地去更新 M 值和 L 值即可. 此時, 我們以邊為基礎, 而不再以頂點為基礎, 那麼影射 R 自然也不再需要. 總結一下 : 設起點為 v_{0}. 一開始令 M(v_{0}) = 0, M(v_{i}) = +\infty, L(v_{i}) = \infty. 對於任意未尋訪的邊 (u, v), 若滿足 M(u) + w(u, v) < M(v), 那麼更新 M(v) = M(u) + w(u, v), L(v) = u. 當每一條邊都被尋訪 \mathop {\mathrm {card}}{V} - 1 次後, 演算法完成. 其中, i = 1, 2, ..., n. 這個演算法被稱為 Bellman-Ford 演算法.

這裡解釋一下為什麼每條邊需要被尋訪 \mathop {\mathrm {card}}{V} - 1 次. 若圖是連通的, 那麼最短路徑至多有 \mathop {\mathrm {card}}{V} - 1 條邊. 而我們已經假設圖中不存在權重之和為負的迴路, 那麼從迴路中去掉某條邊一定會使得權重之和減小而且路徑不再是一條迴路. 假設 v_{0} 到 v_{n} 之間的路徑只有一條, 即 v_{0} \rightarrow v_{1} \rightarrow v_{2} \rightarrow ... \rightarrow v_{n}, 在運氣不好的情況下, 可能只有最後一次更新才能將 v_{n - 1} 和 v_{n} 連接起來. 換句話說, 之前的 \mathop {\mathrm {card}}{V} - 2 次更新都沒有找到 v_{0} 到 v_{n} 的通路, 至多只找到了 v_{0} 到 v_{n - 1} 的通路. 為了避免遺漏 v_{n} 必須還要進行一次更新. 最終, 每條邊需要被尋訪 \mathop {\mathrm {card}}{V} - 1 次.

換個思路. 貪婪演算法在作出決策之後不再更改, 而 Bellman-Ford 演算法是每次都動態地更新所有 M 值, 這正好符合動態規劃演算法 (《動態規劃演算法》) 的思想. 因此, 我們是否可以嘗試使用動態規劃演算法的步驟來解決帶有負值的最短路徑問題呢? 我們將影射 M 改為 M = M(u, k), 表示從起點 v_{0} 到 u 且路徑中共有 k 個頂點的路徑權重. 一開始, 定義 M(v_{0}, 0) = 0, M(v, 0) = +\infty. 其中, v \in V 且 v \neq v_{0}. 對於任意邊 (u, v), 我們都希望 M(u, k - 1) + w(u, v) 是最小的, 這也代表了 M(v, k) 也是最小的. 於是, 我們有動態規劃方程式 \displaystyle {M(v, k) = \min \left \{ M(u, k - 1) + w(u, v) \right \}.} 考慮 M(v, 0), 就有了最終的動態規劃方程式 \displaystyle {M(v, k) = \min \left \{ M(v, 0), \min \left \{ M(u, k - 1) + w(u, v) \right \} \right \}.}

和 Dijkstra 演算法相比, Bellman-Ford 演算法要精簡得多. 在 Bellman-Ford 演算法中, 由於每條邊都會被尋訪 v - 1 次, 因此 Bellman-Ford 演算法的時間複雜度為 \Theta(ve). 由於 Bellman-Ford 演算法和 Dijkstra 演算法一樣, 需要記錄邊是否被尋訪, 也需要記錄影射 M 和 L 的值, 所以空間複雜度也是 \Theta(v + e). 其中, v 是頂點數量, e 是邊的數量.

最後我們討論一下如何判斷權重和為負的迴路. Bellman-Ford 演算法並不能接受圖中存在權重和為負的迴路, 但是演算法並不能保證接受到的圖一定滿足. 如果圖中存在權重和為負的迴路, 那麼 Bellman-Ford 演算法的結果並不是正確的. 當 Bellman-Ford 演算法完成的時候, 我們可以再對邊多進行一次尋訪. 如果圖中不存在權重為負的迴路, 那麼不會有任何節點的 M 值被更新. 但是如果存在權重和為負的迴路, 那麼必定存在某些節點的 M 值繼續被更新, 而且越來越小. 此時, 我們可以直接回傳 Bellman-Ford 演算法失敗的標記.

5.5.3 任意頂點間的最短路徑

當我們要求任意頂點對之間的最短路徑時, 我們可以應用 v 次 Dijkstra 演算法. 此時, 時間複雜度為 \Theta(v^{2} + ve\log {e}). 但是當邊的權重存在負值的時候, Dijkstra 演算法失敗的機率就會大大增加. 如果改用 v 次 Bellman-Ford 演算法, 那麼總體時間複雜度為 \Theta(v^{2}e). 現在, 我們要介紹一種專門用於求不同頂點對之間最短路徑的演算法, 稱之為 Floyd-Warshall 演算法. 和 Bellman-Ford 演算法類似, Floyd-Warshall 演算法可以適用於存在權重為負值的賦權圖, 但是不能存在權重和為負的迴路.

建立影射 M = M(u, v) 表示頂點 u 到 v 之間已知的最短路徑. 初始時, 對於所有邊 (u, v) \in E 及其權重 w(u, v), 初始化 M(u, v) = w(u, v), M(u, u) = 0. 若對於某個頂點 w, 若 M(u, w) + M(w, v) < M(u, v), 說明經過 w 的路徑比一直的路徑更短, 那麼更新 M(u, v) = M(u, w) + M(w, v). 由於任意兩個頂點之間都需要更新, 此處的時間複雜度為 \Theta(v^{2}). 另外, 兩個頂點確定之後, 我們還要檢查是否存在第三個中間頂點, 使得經過中間頂點的路徑是更短的. 因此, Floyd-Warshall 演算法的時間複雜度為 \Theta(v^{3}). 影射 M 實際上是一個矩陣, 記錄了任意兩個頂點之間的最短路徑, 所以 Floyd-Warshall 演算法的空間複雜度為 \Theta(v^{2}). 其中, v 是頂點數量.

由於 Floyd-Warshall 演算法也是動態地進行更新, 所以我們也可以用動態規劃演算法來解決任意頂點間的最短路徑問題.

若圖中有 n 個頂點, 分別給這 n 個頂點編號, 從 1 到 n. 記 M(i, j, k) 表示從第 i 個頂點到第 j 個頂點最短路徑的長度, 路徑上的頂點編號不超過 k. 那麼, 若從第 i 個頂點到第 j 個頂點之間的邊存在, 那麼 M(i, j, 0) = w(v_{i}, v_{j}); 若 i = j, 則 M(i, i, 0) = 0; 若從第 i 個頂點到第 j 個頂點之間的邊不存在, 那麼 M(i, j, 0) = +\infty. 顯然, 當 k = n 時, M(i, j, n) 記錄的必定是第 i 個頂點到第 j 個頂點的最短路徑.

對於 k > 0, 若第 i 個頂點到第 j 個頂點的路徑不包含第 k 個頂點, 那麼路徑長度就是 M(i, j, k - 1) = M(i, j, k); 若第 i 個頂點到第 j 個頂點的路徑包含第 k 個頂點, 那麼路徑長度應該是 M(i, k, k) + M(k, j, k). 兩種可能之間取最小值, 我們就得到了任意頂點間的最短路徑問題當 k > 0 時的動態規劃方程式 \displaystyle {M(i, j, k) = \min \left \{ M(i, j, k - 1), M(i, k, k) + M(k, j, k) \right \}.}

5.6 有向圖中的強連通子圖

任意給定有向圖 \mathcal {G} = (V, E), 我們的目標是找到 \mathcal {G} 中所有強連通子圖. 在強連通子圖中, 從任意頂點 u 出發, 可以到達子圖中的任意其它頂點, 可能到達子圖之外的頂點 v. 但是如果從 u 可以到達 v, 那麼從 v 就一定不能到達 u. 否則, u 和 v 就一定在同一個強連通子圖中.

一種很簡單的方法運用了貪婪演算法 : 逐漸向集合中添加頂點, 添加的條件是該頂點和集合中的其它頂點強連通; 否則, 該頂點無法加入集合, 繼續待定. 最終, 總共有多少個集合, 有向圖就會有多少個強連通子圖. 這種方法的優點是足夠簡單, 但是時間複雜度過高.

在深度優先搜尋法中, 建立一個邊集合 E'. 如果對於一個已尋訪的頂點 u, 存在邊 (u, v) 將頂點 u 和 v 連接起來, 那麼就把 (u, v) 加入 E' 中. 當深度優先搜尋法結束的時候, 子圖 \mathcal {G}' = (V, E') 實際上是一棵生成樹, 我們稱為深度優先搜尋樹 (depth-first search tree, 簡稱為 DFS 樹). 根據樹的後序尋訪規則 (《【資料結構】樹》第 2.3 節), 第一個頂點被尋訪的時候排在第一個, 最後一個頂點尋訪的時候排在最後一個. 因此深度優先搜尋樹的後序尋訪序列中, 若 u 是 v 的祖先節點 (父節點, 父節點的父節點, 父節點的父節點的父節點等等), 那麼只有兩種情況 : \mathcal {G} 中存在從 u 到 v 的通路; 或者 \mathcal {G} 不是連通的, u 和 v 連弱連通都不滿足. 我們不考慮第二種情況, 這種情況下, 可以分別對割裂的子圖運用相關演算法找到連通子子圖即可. 在第一種情況下, 若 u 和 v 處在同一強連通子圖中, 若且唯若 \mathcal {G} 中存在從 v 到 u 的路徑. 這個時候, 我們只需要將 \mathcal {G} 的有向邊全部反向, 然後進行深度優先搜尋. 很顯然, 如果 u 和 v 處在同一個強連通子圖中, 那麼反向之後 u 仍然可以到達 v. 但是如果 u 可以到達 v, 但是 v 無法到達 u, 反向之後從 u 出發是無法再次到達 v 的. 因此, 對於深度優先搜尋樹的後序尋訪序列, 我們只需要將這個序列也反向得到逆向序列, 接著從逆序序列的第一個頂點出發再次進行深度優先搜尋, 還可以到達的頂點必定就在同一個連通子圖中, 到達不了的必定就不在同一個連通子圖中. 把能夠到達的頂點進行相同的獨特標記, 然後從逆向序列中移除, 我們就得到了一個強連通子圖. 當逆向序列中所有頂點都被移除, 我們就得到了 \mathcal {G} 的所有強連通子圖. 這個過程稱為 Kosaraju 演算法.

Kosaraju 演算法進行了兩次深度優先搜尋, 所以時間複雜度是線性的, 為 \Theta(v + e). 而 Kosaraju 演算法還需要標記邊是否被尋訪, 並且使用了雙向佇列或者向量 (《【資料結構】向量 (順序表)》) 來儲存還沒有被尋訪的頂點, 因此空間複雜度為 \Theta(v + e). 其中, v 是頂點數量, e 是邊的數量.

6. 線性結構, 樹結構和圖結構

我們已經講述了所有資料結構 (https://jonny.vip/category/computer-science/data-structure/), 自然要把各種資料結構比較一下. 其實如果細心一些, 我們會發現, 如果圖滿足樹的定義, 那麼圖就是一棵樹; 樹如果滿足線性結構的定義, 那麼樹同時又是線性結構. 因此, 各種資料結構之間實際上是相通的, 大的結構包含了小的結構, 又或者說亂的結構包含了不太亂的結構. 這不僅僅在圖中可以看出來, 當二元搜尋樹可能退化為連結串列的時候 (《【資料結構】樹——AVL 樹》第 0 節) 我們其實已經可以意識到這一點了.

7. 實作

我自己用 C++ 實作了圖 : https://github.com/Jonny0201/data_structure/blob/master/data_structure/graph.hpp, 大家可以參考後自行實作.