C++实现图的DFS核心是递归或栈模拟回溯，需标记已访问节点防重复；邻接表为首选存储结构，递归版简洁直观，非递归版避免栈溢出，连通分量需遍历所有未访问顶点启动DFS。
用C++实现图的DFS，核心是递归或栈模拟回溯过程，关键在于标记已访问节点、避免重复遍历。邻接表是最常用且高效的存储方式。
用邻接表 + 递归实现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; }
用栈实现非递归DFS
避免递归调用栈溢出，更适合大规模图或深度受限环境：
#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++免费学习笔记（深入）”；
- 外层遍历所有顶点 0 到 n−1
- 遇到未访问的，调用一次 dfs()，并计数或记录新连通分量
- 适用于求连通分量个数、最大连通子图大小等
扩展支持有向图与额外信息
只需调整建图方式即可适配有向图；如需记录时间戳（发现/完成时间）、父节点、路径等，可在DFS函数中增加参数或使用结构体封装状态：
- 加一个 parent 参数防止走回头路（在无向图中避免把父节点当新邻居）
- 用两个 vector 分别存 disc（发现时间）和 fin（完成时间）做拓扑排序或找环
- 用 vector
path 记录当前路径，进入时 push_back，退出时 pop_back
基本上就这些。递归写法最常用，非递归更可控，选哪种取决于图规模、栈限制和具体需求。