與深度優先(DFS)演算法原理與多語言實作)
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演算法步驟可歸納為三步將走訪起始頂點start_vet加入佇列並開啟迴圈在迴圈的每輪迭代中彈出佇列首頂點並記錄訪問然後將該頂點的所有鄰接頂點加入到佇列尾部迴圈步驟 2直到所有頂點被訪問完畢後結束。程式碼相對抽象建議對照倉庫中的逐步示意圖來加深理解graph_bfs_step1.png 至 graph_bfs_step11.png 完整展示了從起點出發、逐層擴張直至所有頂點入列的整個過程。visited 集合防止重複走訪的關鍵為了防止重複走訪頂點我們需要藉助一個雜湊集合Hash Setvisited來記錄哪些節點已被訪問。!!! tip雜湊集合可以看作一個只儲存 key 而不儲存 value 的雜湊表它可以在 $O(1)$ 時間複雜度下進行 key 的增刪查改操作。根據 key 的唯一性雜湊集合通常用於資料去重等場景。在上述 Python 程式碼中visited的使用有兩個細微但重要的設計點起始頂點start_vet在入列同時就被加入visitedvisited setVertex避免起點在後續迴圈中被重複處理鄰接頂點adj_vet在入列時就被標記為已訪問visited.add(adj_vet)而不是在出列時才標記。這樣可以防止同一頂點被多個鄰居重複入列保證每個頂點至多入隊一次。從頂點類別 vertex.py可以看到Vertex是簡單的值包裝類別Python 的set依賴其雜湊性即可完成去重。在 Java 實作 graph_bfs.java 中對應的結構是SetVertex visited new HashSet()搭配QueueVertex 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 ListVertex graphBFS(GraphAdjList graph, Vertex startVet) { ListVertex res new ArrayList(); SetVertex visited new HashSet(); visited.add(startVet); QueueVertex 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创作声明:本文部分内容由AI辅助生成(AIGC),仅供参考