408答疑

---

---

三、圖的遍歷

圖的遍歷概述

圖的遍歷是指從圖中的某一項點出發，按照某種搜索方法沿著圖中的邊對圖中的所有頂點訪問一次，且僅訪問一次。
注意到樹是一種特殊的圖，所以樹的遍歷實際上也可視為一種特殊的圖的遍歷。

圖的遍歷算法的重要性

圖的遍歷算法是求解圖的連通性問題、拓撲排序和求關鍵路徑等算法的基礎。

圖的遍歷與樹的遍歷的區別

圖的遍歷比樹的遍歷要復雜得多，因為圖的任意一個頂點都可能和其余的頂點相鄰接，所以在訪問某個頂點后，可能沿著某條路徑搜索又回到該頂點。

圖的遍歷過程中的注意事項

避免重復訪問

為避免同一頂點被訪問多次，在遍歷圖的過程中，必須記下每個已訪問過的頂點，為此可以設一個輔助數組 visited[] 來標記頂點是否被訪問過。

遍歷算法的分類

圖的遍歷算法主要有兩種：

• 廣度優先搜索（BFS）
• 深度優先搜索（DFS）

遍歷結果的不唯一性

圖的遍歷結果順序是不唯一的，跟選擇的起始結點和所求鄰接結點的順序有關。

廣度優先搜索

廣度優先搜索（BFS）概述

廣度優先搜索（Breadth-First-Search, BFS）類似于二叉樹的層次遍歷算法。基本思想是：首先訪問起始頂點 $v$，接著由 $v$ 出發，依次訪問 $v$ 的各個未訪問過的鄰接頂點 $w_1,w_2,?,w_r$，然后依次訪問 $w_1,w_2,?,w_r$ 的所有未被訪問過的鄰接頂點；再從這些訪問過的頂點出發，訪問它們所有未被訪問過的鄰接頂點，直至圖中所有頂點都被訪問過為止。若此時圖中尚有頂點未被訪問，則另選圖中一個未曾被訪問的頂點作為始點，重復上述過程，直至圖中所有頂點都被訪問到為止。Dijkstra 單源最短路徑算法和 Prim 最小生成樹算法也應用了類似的思想。

BFS 的特點

廣度優先搜索遍歷圖的過程是以 $v$ 為起始點，由近至遠依次訪問和 $v$ 有路徑相通且路徑長度為 1, 2, … 的頂點。廣度優先搜索是一種分層的查找過程，每向前走一步可能訪問一批頂點，不像深度優先搜索那樣有往回退的情況，因此它不是一個遞歸的算法。為了實現逐層的訪問，算法必須借助一個輔助隊列，以記憶正在訪問的頂點的下一層頂點。

廣度優先遍歷的過程

示例圖

如下圖所示，一個無向圖 $G$。

遍歷過程

假設從頂點 $a$ 開始訪問，$a$ 先入隊。此時隊列非空，取出隊頭元素 $a$，因為 $b,c$ 與 $a$ 鄰接且未被訪問過，于是依次訪問 $b,c$，并將 $b,c$ 依次入隊。隊列非空，取出隊頭元素 $b$，依次訪問與 $b$ 鄰接且未被訪問的頂點 $d,e$，并將 $d,e$ 入隊（注意：$a$ 與 $b$ 也鄰接，但 $a$ 已置訪問標記，所以不再重復訪問）。此時隊列非空，取出隊頭元素 $c$，訪問與 $c$ 鄰接且未被訪問的頂點 $f,g$，并將 $f,g$ 入隊。此時，取出隊頭元素 $d$，但與 $d$ 鄰接且未被訪問的頂點為空，所以不進行任何操作。繼續取出隊頭元素 $e$，將 $h$ 入隊列……最終取出隊頭元素 $h$ 后，隊列為空，從而循環自動跳出。遍歷結果為 $abcdefgh$。

從上例不難看出，圖的廣度優先搜索的過程與二叉樹的層次遍歷是完全一致的，這也說明了圖的廣度優先搜索遍歷算法是二叉樹的層次遍歷算法的擴展。

BFS 算法的性能分析

無論是鄰接表還是鄰接矩陣的存儲方式，BFS 算法都需要借助一個輔助隊列 $Q$，$n$ 個頂點均需入隊一次，在最壞的情況下，空間復雜度為 $O(|V|)$。

基于鄰接表存儲的 BFS 的效率

遍歷圖的過程實質上是對每個頂點查找其鄰接點的過程，耗費的時間取決于所采用的存儲結構。采用鄰接表存儲時，每個頂點均需搜索（或入隊）一次，時間復雜度為 $O(|V|)$，在搜索每個頂點的鄰接點時，每條邊至少訪問一次，時間復雜度為 $O(|E|)$，總的時間復雜度為 $O(|V|+|E|)$。采用鄰接矩陣存儲時，查找每個頂點的鄰接點所需的時間為 $O(|V|)$，總時間復雜度為 $O(|V{|}^2)$。

BFS 算法求解單源最短路徑問題

若圖 $G=(V,E)$ 為非帶權圖，定義從頂點 $u$ 到頂點 $v$ 的最短路徑 $d(u,v)$ 為從 $u$ 到 $v$ 的任何路徑中最少的邊數；若從 $u$ 到 $v$ 沒有通路，則 $d(u,v)=\infty$。

使用 BFS，我們可以求解一個滿足上述定義的非帶權圖的單源最短路徑問題，這是由廣度優先搜索總是按照距離由近到遠來遍歷圖中每個頂點的性質決定的。

廣度優先生成樹

在廣度遍歷的過程中，我們可以得到一棵遍歷樹，稱為廣度優先生成樹，如下圖所示。

需要注意的是，同一個圖的鄰接矩陣存儲表示是唯一的，所以其廣度優先生成樹也是唯一的，但因為鄰接表存儲表示不唯一，所以其廣度優先生成樹也是不唯一的。

深度優先搜索

深度優先搜索（DFS）概述

深度優先搜索（Depth-First-Search, DFS）是一種盡可能“深”地搜索圖的算法。其基本思想如下：

1. 借助臨時空間：借助 $n$ 個臨時空間來標記結點是否被訪問過。
2. 訪問頂點：首先訪問圖中的某一頂點 $v$，接著訪問 $v$ 的鄰接頂點 $w$，訪問 $w$ 的下一鄰接頂點，依次類推，重復上述過程。
3. 回溯：當不能再繼續向下訪問頂點時，依次退回到最近被訪問的頂點，如果還有其他鄰接頂點沒有被訪問，則繼續從該結點出發開始上述的遍歷過程，直到圖的所有結點被訪問完為止。

深度優先遍歷相當于二叉樹中的前序遍歷。

深度優先遍歷的過程

示例圖

如下圖所示，一個無向圖 $G$。

遍歷過程

深度優先搜索的過程如下：

1. 首先訪問 $a$，并置 $a$ 訪問標記。
2. 然后訪問與 $a$ 鄰接且未被訪問的頂點 $b$，置 $b$ 訪問標記。
3. 然后訪問與 $b$ 鄰接且未被訪問的頂點 $d$，置 $d$ 訪問標記。
4. 此時 $d$ 已沒有未被訪問過的鄰接點，所以返回上一個訪問的頂點 $b$，訪問與其鄰接且未被訪問的頂點 $e$，置 $e$ 訪問標記，以此類推，直至圖中所有頂點都被訪問一次。遍歷結果為 $abdehcfg$。

DFS 算法的性能分析

DFS算法是一個遞歸算法，需要借助一個遞歸工作棧，所以其空間復雜度為 $O(|V|)$。遍歷圖的過程實質上是通過邊查找鄰接點的過程，因此兩種遍歷方式的時間復雜度都相同，不同之處僅在于對頂點訪問順序的不同。采用鄰接矩陣存儲時，總時間復雜度為 $O(|V{|}^2)$。采用鄰接表存儲時，總的時間復雜度為 $O(|V|+|E|)$。

深度優先的生成樹和生成森林

與廣度優先搜索一樣，深度優先搜索也會產生一棵深度優先生成樹。當然，這是有條件的，即對連通圖調用DFS才能產生深度優先生成樹，否則產生的將是深度優先生成森林，如下圖所示。

與BFS類似，基于鄰接表存儲的深度優先生成樹是不唯一的。

注意事項

圖的鄰接矩陣表示是唯一的，但對鄰接表來說，若邊的輸入次序不同，則生成的鄰接表也不同。因此，對同樣一個圖，基于鄰接矩陣的遍歷得到的 DFS 序列和 BFS 序列是唯一的，基于鄰接表的遍歷得到的 DFS 序列和 BFS 序列是不唯一的。

圖的遍歷與圖的連通性

圖的遍歷法可以用來判斷圖的連通性。對于無向圖來說，若無向圖是連通的，則從任意一個結點出發，僅需一次遍歷就能夠訪問圖中的所有頂點；若無向圖是非連通的，則從某一個頂點出發，一次遍歷只能訪問到該頂點所在連通分量的所有頂點，而對于圖中其他連通分量的頂點，則無法通過這次遍歷訪問。對于有向圖來說，若從初始頂點到圖中的每個頂點都有路徑，則能夠訪問到圖中的所有頂點，否則不能訪問到所有頂點。

因此，在BFSTraverse()或DFSTraverse()中添加了第二個for循環，再選取初始點，繼續進行遍歷，以防止一次無法遍歷圖的所有頂點。對于無向圖，上述兩個函數調用BFS(G, i)或DFS(G, i)的次數等于該圖的連通分量數；而對于有向圖則不是這樣，因為一個連通的有向圖分為強連通的和非強連通的，它的連通子圖也分為強連通分量和非強連通分量，非強連通分量一次調用BFS(G, i)或DFS(G, i)無法訪問到該連通分量的所有頂點，如下圖所示。

六、參考資料

鮑魚科技課件

b站免費王道課后題講解:

網課全程班:

26王道考研書