C++如何实现图的深度优先搜索（DFS）？（代码示例）

9次阅读

C++ 实现图的 DFS 核心是递归或栈模拟回溯，需标记已访问节点防重复；邻接表为首选存储结构，递归版简洁直观，非递归版避免栈溢出，连通分量需遍历所有未访问顶点启动 DFS。

C++ 如何实现图的深度优先搜索（DFS）？（代码示例）

用 C ++ 实现图的 DFS，核心是递归或栈模拟回溯过程，关键在于标记已访问节点、避免重复遍历。邻接表是最常用且高效的存储方式。

适合大多数场景，代码简洁，逻辑直观。假设图是无向图，顶点编号从 0 开始：

#include <iostream> #include <vector> using namespace std;  void dfs(int u, vector<bool>& visited, const vector<vector<int>>& graph) {visited[u] = true;     cout << u << " ";  // 访问操作（可替换为其他处理）for (int v : graph[u]) {if (!visited[v]) {dfs(v, visited, graph);         }     } }  int main() {     int n = 6;  // 顶点数     vector<vector<int>> graph(n);     // 添加边：0-1, 0-2, 1-3, 1-4, 2-5     graph[0] = {1, 2};     graph[1] = {0, 3, 4};     graph[2] = {0, 5};     graph[3] = {1};     graph[4] = {1};     graph[5] = {2};      vector<bool> visited(n, false);     cout << "DFS 遍历顺序： ";     dfs(0, visited, graph);  // 从顶点 0 开始     cout << endl;     return 0; }

避免递归调用栈溢出，更适合大规模图或深度受限环境：

#include <iostream> #include <vector> #include <stack> using namespace std;  void dfs_iterative(int start, const vector<vector<int>>& graph) {int n = graph.size();     vector<bool> visited(n, false);     stack<int> st;          st.push(start);     visited[start] = true;     cout << start << " ";      while (!st.empty()) {int u = st.top();         st.pop();          // 注意：这里要倒序遍历邻接点，才能和递归版顺序一致（可选）for (auto it = graph[u].rbegin(); it != graph[u].rend(); ++it) {int v = *it;             if (!visited[v]) {visited[v] = true;                 cout << v << " ";                 st.push(v);             }         }     } }

实际图可能不连通，需对每个未访问节点启动一次 DFS：

立即学习“C++ 免费学习笔记（深入）”；