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
基本上就这些。递归写法最常用，非递归更可控，选哪种取决于图规模、栈限制和具体需求。
