DFS在C++中需靠显式状态控制，邻接表递归必须传节点索引并用引用visited防重入；手动栈需压栈前标记访问；树可省visited，图必须用；慎用vector。
DFS 在 C++ 中不是靠“教程逻辑”驱动的，而是靠明确的状态控制和递归终止条件；写错往往是因为没管住访问标记或忽略图的存储结构差异。
用 vector<vector>></vector> 存邻接表时怎么写 DFS 递归
这是最常用也最容易出错的场景：邻接表本身不带节点 ID，递归函数必须显式传入当前节点索引，并用外部 visited 数组防重入。
-
visited必须是全局或引用传入，不能在每次递归里新建 - 遍历邻居要写成
for (int neighbor : graph[u])，别手抖写成for (int i = 0; i - 递归前必须先设
visited[u] = true，否则可能重复进入同一节点
void dfs(int u, const vector<vector<int>>& graph, vector<bool>& visited) {
visited[u] = true;
for (int v : graph[u]) {
if (!visited[v]) {
dfs(v, graph, visited);
}
}
}
遇到 std::stack<int></int> 手动模拟栈时要注意什么
递归本质是系统栈，手动栈容易漏掉“已访问但未处理完”的状态。非递归 DFS 不等于把递归改成 while + stack 就完事。
- 压栈前就要标记
visited[u] = true，否则同一节点可能被多次压入 - 出栈后才处理该节点（比如输出、收集），但邻居的访问判断仍依赖
visited - 如果要还原路径或记录深度，得额外存
pair<int int></int>（节点+深度），不能只压节点
DFS 遍历树和遍历一般图的区别在哪
树无环、有向且连通，所以不需要 visited 数组也能跑通；但只要图里存在环或多个连通分量，不加访问控制就会无限递归或漏节点。
立即学习“C++免费学习笔记（深入）”；
- 树：可直接用
dfs(root)，子节点天然不回指父节点 - 一般图：必须用
visited，且初始化要覆盖全部可能节点编号（比如 0~n-1） - 无向图边存两次，
graph[u].push_back(v)和graph[v].push_back(u)缺一不可
为什么用 vector<bool></bool> 做访问数组有时会慢还出错
vector<bool></bool> 是特化模板，内部按位存储，operator[] 返回的是代理对象而非引用，可能导致 visited[i] = true 失效。
- 调试时发现某节点反复进入？优先换成
vector<char></char>或vector<int></int> - 性能敏感场景（比如百万节点），位操作反而因 cache 不友好变慢
- Clang/GCC 对
vector<bool></bool>的迭代器行为也有差异，跨平台项目尽量避开
真正卡住人的从来不是“怎么写递归”，而是没想清楚图的输入形式、节点编号范围、是否带权、有向还是无向——这些决定了 visited 数组大小、邻接表构造方式、以及要不要加额外状态字段。
