优先用迭代，因递归在深度超限时易栈溢出，而迭代用std::stack可控内存、支持中断调试；关键需正确标记访问状态并按序压栈。
DFS 用递归还是迭代？选错会影响栈溢出风险
递归写法最直观，但图节点数超过几万时容易爆栈；迭代用 std::stack 更可控，尤其在嵌入式或内存受限环境。实际项目中，如果图结构深度不确定，优先用迭代——哪怕多写几行代码。
常见错误是递归没设访问标记，导致无限循环。比如邻接表存了双向边，dfs(1) 调 dfs(2)，后者又调回 dfs(1)，直接卡死。
- 必须用
std::vector<bool> visited</bool>或std::unordered_set<int></int>记录已访问节点 - 递归版本入口要手动调用一次
dfs(start)，不能只写函数定义就完事 - 迭代版本里，每次从
stack.pop()取出节点后，立刻标记为已访问，否则同一节点可能被压栈多次
邻接表 vs 邻接矩阵：选哪种存图影响 DFS 性能
邻接表（std::vector<:vector>></:vector>）适合稀疏图，遍历邻居时间复杂度是 O(度数)，总时间接近 O(V + E)；邻接矩阵（std::vector<:vector>></:vector>）查边快（O(1)），但遍历所有邻居固定 O(V)，稠密图才划算。
多数实际场景——比如社交关系、文件依赖、迷宫——都是稀疏的，直接用邻接表。别为了“看着整齐”硬上矩阵。
- 邻接表初始化：先 resize
graph到n+1，再对每条边u->v执行graph[u].push_back(v) - 无向图记得双向加边：
graph[u].push_back(v); graph[v].push_back(u); - 如果节点编号不连续（比如 ID 是字符串或大整数），改用
std::unordered_map<:string std::vector>></:string>
如何让 DFS 返回路径而不是只打印节点
单纯遍历只要输出或计数，但很多问题（如找连通分量、解迷宫、拓扑排序）需要完整路径。关键是在递归/迭代过程中维护当前路径状态。
递归版最简单：把 std::vector<int>& path</int> 作为引用参数传入，进入节点时 push_back，退出前 pop_back；迭代版则要在栈里存 std::pair<int std::vector>></int> 或额外用一个 parent 数组反向追溯。
- 路径记录必须和访问标记同步：只有当节点首次被访问（即未在
visited中）才加入路径 - 找到目标后立即
return true并停止后续递归，否则会继续搜完所有分支 - 若需所有路径（比如所有从 A 到 B 的路线），去掉提前返回，用
std::vector<:vector>></:vector>收集结果
DFS 在有环图中崩溃？检查这三处标记逻辑
报错不是 “segmentation fault” 就是程序卡住不动，八成是访问标记没生效。最典型的是：标记写在 for 循环外、判断条件写反、或者用了局部变量覆盖全局状态。
例如：if (!visited[v]) { visited[v] = true; dfs(v); } 这是对的；但写成 if (!visited[v]) { dfs(v); visited[v] = true; } 就错——递归进去后可能重复访问 v。
- 标记操作必须在进入子节点前完成，且仅执行一次
- 不要在递归函数开头写
if (visited[node]) return;—— 这会导致刚进来的节点被跳过 - 多线程环境下，
visited必须是线程局部或加锁，否则出现竞态导致漏标
真正麻烦的不是写法，而是图数据本身带自环或重边——预处理时用 std::set 去重比在 DFS 里硬扛更稳妥。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
