递归dfs中visited数组需按节点编号范围初始化为visited(n+1)并显式赋false，且必须为全局/类成员或引用传递；栈模拟dfs需倒序压栈以复现递归顺序；无向图需预处理自环，找环等场景须加parent参数区分树边与反向边。
递归实现DFS时，visited数组必须按节点编号范围初始化
递归写法最直观，但新手常因visited大小不对导致越界或漏访。比如图有10个节点，编号是1~10，却用vector<bool> visited(10)</bool>——这实际只覆盖0~9，节点10会访问visited[10]越界；若编号从1开始，应设为visited(n + 1)（n为最大节点编号）。
另一个常见问题是把visited声明在递归函数内部：每次调用都新建一份，状态无法传递。它必须是全局变量、类成员，或通过引用传入。
-
visited长度 ≥ 所有出现过的节点编号最大值 + 1 - 初始化全部为
false，别依赖默认值（vector<bool></bool>默认是false，但显式赋值更安全） - 递归函数参数中，除
u（当前节点），必须带vector<bool>& visited</bool>和const vector<vector>>& graph</vector>
用栈模拟DFS时，stack里存什么决定遍历顺序
标准DFS要求“一条路走到黑”，但用stack手动模拟时，压栈顺序直接影响结果。例如邻接表graph[u] = {2, 1, 3}，若顺序压入2、1、3，出栈是3→1→2，等价于访问顺序反向；若想复现递归行为（即先访2），得倒序压栈：for (int i = graph[u].size()-1; i >= 0; i--) stack.push(graph[u][i])。
不处理顺序会导致路径树结构不同，虽仍算DFS（连通性、时间戳等逻辑正确），但调试时和递归版本对不上，容易误判bug。
- 用
stack<int></int>，只存节点编号，别存边或额外状态（除非需要路径回溯） - 每个节点入栈前必须检查
!visited[v]，避免重复压栈 - 标记
visited的时机：应在入栈时标记（而非出栈时），否则同一节点可能被多次压入
无向图DFS要防自环与双向边重复访问
邻接表存无向图时，u→v和v→u都存在。若仅靠visited，从u到v后，v的邻接表里还有u，会试图返回——但此时visited[u]已是true，自然跳过。这没问题。真正危险的是自环边（u→u）或重边：若图含u→u且未过滤，会无限递归或死循环。
实践中建议预处理：建图时就跳过u == v的边；若需保留自环（如某些状态图），则在DFS内加判断if (v == u) continue。
- 读入边时，
if (u != v) graph[u].push_back(v);（无向图需两边都加，但同样跳过自环） - 不依赖“
visited能拦住一切”——自环不改变visited状态，必须显式排除 - 重边不影响正确性，但可去重提升效率：
set或sort + unique邻接表
DFS遍历中，parent参数比visited更能区分树边与反向边
做连通分量或找环时，单靠visited只能知道“是否访问过”，但无法判断v是父节点（刚来的那条边）还是其他祖先——这会导致把树边误判为反向边。解决方法是在递归参数中加int parent，访问邻居时跳过parent即可。
例如从u=2调用dfs(3, 2)，在dfs(3, 2)中遍历到v=2，直接if (v == parent) continue，不把它当环边处理。这个技巧在求桥、割点、无向图环检测中必不可少。
- 递归调用写成
dfs(v, u)，明确u是v的父节点 -
parent初始值设为-1（假设节点编号≥0），进入后先检查if (v == parent) - 不要用
visited替代parent逻辑——前者管全局访问，后者管局部拓扑关系
递归DFS简洁，但深图易爆栈；栈模拟灵活，但顺序和标记时机稍不留神就偏移语义。真正难的不是写出两种形式，而是根据问题需求选对变体：查连通性？用基础版；找环？加parent；需路径还原？栈里存pair<int int></int>记录上一跳。这些细节没对齐，结果看起来“差不多”，实则逻辑已偏。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
