企业官网建设流程全解析

Hello 算法圖的走訪全解析：廣度優先（BFS）與深度優先（DFS）演算法原理與多語言實作

【免费下载链接】hello-algo《Hello 算法》：动画图解、一键运行的数据结构与算法教程。支持简中、繁中、English、日本語，提供 Python, Java, C++, C, C#, JS, Go, Swift, Rust, Ruby, Kotlin, TS, Dart 等代码实现项目地址: https://gitcode.com/GitHub_Trending/he/hello-algo

本篇技術指南以《Hello 算法》繁中版 圖的走訪 章節為核心，系統講解圖的兩種基本走訪方式——廣度優先走訪（BFS）與深度優先走訪（DFS）的演算法思想、實作流程與複雜度分析，並結合倉庫內 graph_bfs.py、graph_dfs.py 等真實原始碼逐行剖析。讀完本篇，你將掌握「由近及遠」與「走到底再回頭」兩種走訪範式，理解佇列與雜湊集合在走訪中的關鍵作用，並能獨立分析走訪序列的唯一性與時空複雜度。

從樹到圖：為什麼需要走訪演算法

在圖一章中我們知道，樹代表的是「一對多」的關係，而圖具有更高的自由度，可以表示任意的「多對多」關係。因此，可以把樹看作圖的一種特例，樹的走訪操作也是圖的走訪操作的一種特例。

無論是樹還是圖，都需要應用搜索演算法來實現走訪操作。圖的走訪方式可分為兩種：

• 廣度優先走訪（Breadth-First Traversal）
• 深度優先走訪（Depth-First Traversal）

廣度優先走訪

廣度優先走訪是一種由近及遠的走訪方式，從某個節點出發，始終優先訪問距離最近的頂點，並一層層向外擴張。如下圖所示，從左上角頂點出發，首先走訪該頂點的所有鄰接頂點，然後走訪下一個頂點的所有鄰接頂點，以此類推，直至所有頂點訪問完畢。

演算法實現

BFS 通常藉助**佇列（Queue）**來實現。佇列具有「先入先出（FIFO）」的性質，這與 BFS 的「由近及遠」的思想異曲同工。以 Python 實作 graph_bfs.py 為例，完整流程如下：

def graph_bfs(graph: GraphAdjList, start_vet: Vertex) -> list[Vertex]: """廣度優先走訪""" # 使用鄰接表來表示圖，以便獲取指定頂點的所有鄰接頂點 # 頂點走訪序列 res = [] # 雜湊集合，用於記錄已被訪問過的頂點 visited = setVertex # 佇列用於實現 BFS que = dequeVertex # 以頂點 vet 為起點，迴圈直至訪問完所有頂點 while len(que) > 0: vet = que.popleft() # 佇列首頂點出隊 res.append(vet) # 記錄訪問頂點 # 走訪該頂點的所有鄰接頂點 for adj_vet in graph.adj_list[vet]: if adj_vet in visited: continue # 跳過已被訪問的頂點 que.append(adj_vet) # 只入列未訪問的頂點 visited.add(adj_vet) # 標記該頂點已被訪問 # 返回頂點走訪序列 return res

演算法步驟可歸納為三步：

1. 將走訪起始頂點start_vet加入佇列，並開啟迴圈；
2. 在迴圈的每輪迭代中，彈出佇列首頂點並記錄訪問，然後將該頂點的所有鄰接頂點加入到佇列尾部；
3. 迴圈步驟 2，直到所有頂點被訪問完畢後結束。

程式碼相對抽象，建議對照倉庫中的逐步示意圖來加深理解：graph_bfs_step1.png 至 graph_bfs_step11.png 完整展示了從起點出發、逐層擴張直至所有頂點入列的整個過程。

visited 集合：防止重複走訪的關鍵

為了防止重複走訪頂點，我們需要藉助一個雜湊集合（Hash Set）visited來記錄哪些節點已被訪問。

!!! tip

雜湊集合可以看作一個只儲存 `key` 而不儲存 `value` 的雜湊表，它可以在 $O(1)$ 時間複雜度下進行 `key` 的增刪查改操作。根據 `key` 的唯一性，雜湊集合通常用於資料去重等場景。

在上述 Python 程式碼中，visited的使用有兩個細微但重要的設計點：

• 起始頂點start_vet在入列同時就被加入visited（visited = setVertex），避免起點在後續迴圈中被重複處理；
• 鄰接頂點adj_vet在入列時就被標記為已訪問（visited.add(adj_vet)），而不是在出列時才標記。這樣可以防止同一頂點被多個鄰居重複入列，保證每個頂點至多入隊一次。

從頂點類別 vertex.py可以看到，Vertex是簡單的值包裝類別，Python 的set依賴其雜湊性即可完成去重。在 Java 實作 graph_bfs.java 中，對應的結構是Set<Vertex> visited = new HashSet<>()搭配Queue<Vertex> que = new LinkedList<>()，邏輯與 Python 版完全一致，方便讀者對照不同語言的同一演算法。

廣度優先走訪的序列是否唯一？

不唯一。廣度優先走訪只要求按「由近及遠」的順序走訪，而多個相同距離的頂點的走訪順序允許被任意打亂。以文中示例圖為例，頂點 $1$、$3$ 的訪問順序可以交換，頂點 $2$、$4$、$6$ 的訪問順序也可以任意交換。

這意味著 BFS 演算法保證的是「層次」的確定性，而非「頂點序列」的確定性——只要所有較近的頂點先於較遠的頂點被訪問，任意合法的頂點次序都是有效的廣度優先走訪。

複雜度分析

設圖的頂點數量為 $|V|$、邊數量為 $|E|$：

• 時間複雜度：所有頂點都會入列並出隊一次，使用 $O(|V|)$ 時間；在走訪鄰接頂點的過程中，由於是無向圖，因此所有邊都會被訪問 $2$ 次，使用 $O(2|E|)$ 時間；總體使用 $O(|V| + |E|)$ 時間。
• 空間複雜度：串列res、雜湊集合visited、佇列que中的頂點數量最多為 $|V|$，使用 $O(|V|)$ 空間。

深度優先走訪

深度優先走訪是一種優先走到底、無路可走再回頭的走訪方式。如下圖所示，從左上角頂點出發，訪問當前頂點的某個鄰接頂點，直到走到盡頭時返回，再繼續走到盡頭並返回，以此類推，直至所有頂點走訪完成。

演算法實現

這種「走到盡頭再返回」的演算法範式通常基於遞迴來實現。與廣度優先走訪類似，在深度優先走訪中，我們也需要藉助一個雜湊集合visited來記錄已被訪問的頂點，以避免重複訪問頂點。

倉庫中的 Python 實作 graph_dfs.py 將遞迴邏輯封裝在輔助函式dfs()中，而對外提供graph_dfs()入口：

def dfs(graph: GraphAdjList, visited: set[Vertex], res: list[Vertex], vet: Vertex): """深度優先走訪輔助函式""" res.append(vet) # 記錄訪問頂點 visited.add(vet) # 標記該頂點已被訪問 # 走訪該頂點的所有鄰接頂點 for adjVet in graph.adj_list[vet]: if adjVet in visited: continue # 跳過已被訪問的頂點 # 遞迴訪問鄰接頂點 dfs(graph, visited, res, adjVet) def graph_dfs(graph: GraphAdjList, start_vet: Vertex) -> list[Vertex]: """深度優先走訪""" # 使用鄰接表來表示圖，以便獲取指定頂點的所有鄰接頂點 # 頂點走訪序列 res = [] # 雜湊集合，用於記錄已被訪問過的頂點 visited = set[Vertex]() dfs(graph, visited, res, start_vet) return res

注意與 BFS 的一個差異：BFS 的visited在入列時就標記，而 DFS 的visited在進入遞迴時（訪問頂點當下）標記。兩者都保證了「每個頂點只被處理一次」，只是配合的容器（佇列 vs 呼叫堆疊）不同。

深度優先走訪的演算法流程可透過遞推與回溯兩個階段理解：

• 直虛線代表向下遞推，表示開啟了一個新的遞迴方法來訪問新頂點；
• 曲虛線代表向上回溯，表示此遞迴方法已經返回，回溯到了開啟此方法的位置。

為了加深理解，建議將逐步示意圖與程式碼結合起來，在腦中模擬（或者用筆畫下來）整個 DFS 過程，包括每個遞迴方法何時開啟、何時返回。倉庫中提供了完整的逐步圖解：graph_dfs_step1.png 至 graph_dfs_step11.png。

深度優先走訪的序列是否唯一？

與廣度優先走訪類似，深度優先走訪序列的順序也不是唯一的。給定某頂點，先往哪個方向探索都可以，即鄰接頂點的順序可以任意打亂，都是深度優先走訪。

以樹的走訪為例，「根 → 左 → 右」「左 → 根 → 右」「左 → 右 → 根」分別對應前序、中序、後序走訪，它們展示了三種走訪優先順序，然而這三者都屬於深度優先走訪。這也再次印證了開篇的結論：樹是圖的特例，樹的走訪是圖的走訪的特例。

複雜度分析

• 時間複雜度：所有頂點都會被訪問 $1$ 次，使用 $O(|V|)$ 時間；所有邊都會被訪問 $2$ 次，使用 $O(2|E|)$ 時間；總體使用 $O(|V| + |E|)$ 時間。
• 空間複雜度：串列res、雜湊集合visited頂點數量最多為 $|V|$，遞迴深度最大為 $|V|$，因此使用 $O(|V|)$ 空間。

深入底層：鄰接表如何支撐走訪

兩種走訪演算法的核心操作都是「獲取某頂點的所有鄰接頂點」，這依賴於圖的儲存結構。倉庫中的 graph_adjacency_list.py 使用鄰接表儲存無向圖：

• self.adj_list是一個雜湊表，key為頂點，value為該頂點的所有鄰接頂點串列；
• 建構子接受邊集合edges，依次呼叫add_vertex()與add_edge()完成建圖；
• add_edge()會同時在兩個頂點的鄰接串列中互相添加對方，體現無向圖邊的「雙向」性質。

BFS 與 DFS 的程式碼中都直接走訪graph.adj_list[vet]來枚舉鄰居，這一行的效率直接決定走訪的時間複雜度。正因如此，graph.md 中才強調：鄰接表的時間效率不如鄰接矩陣，但更節省空間；當鄰接表中的串列過長時，可以將其轉化為 AVL 樹、紅黑樹甚至雜湊表來優化查詢效率。

另外，測試驅動程式碼中使用了vals_to_vets()與vets_to_vals()這對輔助函式（定義於 vertex.py），在「整數值」與「頂點物件」之間相互轉換，便於直接以[0, 1, 2, ..., 9]這樣的值串列建圖、以值串列輸出走訪結果。

多語言對照與執行方式

《Hello 算法》為圖的走訪提供了 Python、Java、C++、C、C#、JavaScript、TypeScript、Go、Swift、Rust、Ruby、Kotlin、Dart 等主流語言的同構實作，存放於zh-hant/codes/<語言>/chapter_graph/目錄下。以 Java 版 graph_bfs.java 為例，其主流程與 Python 版一一對應：

static List<Vertex> graphBFS(GraphAdjList graph, Vertex startVet) { List<Vertex> res = new ArrayList<>(); Set<Vertex> visited = new HashSet<>(); visited.add(startVet); Queue<Vertex> que = new LinkedList<>(); que.offer(startVet); while (!que.isEmpty()) { Vertex vet = que.poll(); // 佇列首頂點出隊 res.add(vet); // 記錄訪問頂點 for (Vertex adjVet : graph.adjList.get(vet)) { if (visited.contains(adjVet)) continue; // 跳過已被訪問的頂點 que.offer(adjVet); // 只入列未訪問的頂點 visited.add(adjVet); // 標記該頂點已被訪問 } } return res; }

閱讀時可以選定一種熟悉的語言為主線，再與其他語言版本對照，重點觀察「佇列／集合／遞迴」三要素在不同語言中的對應寫法（如 Python 的deque、Java 的LinkedList佇列、C++ 的queue等），這正是本倉庫「一鍵執行、多語言對照」設計的價值所在。

重點回顧

結合小結中的核心結論，本篇要點總結如下：

• 樹是圖的一種特例，樹的走訪也是圖的走訪的一種特例；
• 圖的廣度優先走訪是一種由近及遠、層層擴張的搜索方式，通常藉助佇列實現；
• 圖的深度優先走訪是一種優先走到底、無路可走時再回溯的搜索方式，常基於遞迴來實現；
• 兩種走訪都需要雜湊集合visited防止重複訪問，其時間複雜度均為 $O(|V| + |E|)$，空間複雜度均為 $O(|V|)$；
• 兩種走訪的頂點序列均不唯一：BFS 允許同層頂點次序打亂，DFS 允許鄰接頂點的探索方向任意；
• 在非連通圖中，從某個頂點出發至少有一個頂點無法到達，走訪非連通圖需要設定多個起點，以走訪到圖的所有連通分量。

掌握 BFS 與 DFS 之後，可以進一步深入圖的走訪章節周邊的圖操作知識，並在圖的表示中理解鄰接矩陣與鄰接表對走訪效率的影響，為後續學習最短路徑、拓撲排序等圖演算法打下基礎。

【免费下载链接】hello-algo《Hello 算法》：动画图解、一键运行的数据结构与算法教程。支持简中、繁中、English、日本語，提供 Python, Java, C++, C, C#, JS, Go, Swift, Rust, Ruby, Kotlin, TS, Dart 等代码实现项目地址: https://gitcode.com/GitHub_Trending/he/hello-algo