递归DFS需初始化visited数组并在进入前检查越界和访问状态，非递归DFS用stack模拟并压栈前标记visited，回溯DFS须成对操作状态变量且剪枝前置。
直接用递归实现 DFS 最简洁，但要注意栈溢出和访问标记的时机；非递归版本用 stack 模拟更可控，适合图很大或深度不确定的场景。
递归 DFS：必须初始化 visited 数组并检查边界
递归写法最符合 DFS 直观逻辑，但容易漏掉两个关键点：一是未初始化 visited 数组导致重复访问，二是没在进入递归前检查索引越界或节点合法性。
-
visited必须在调用 DFS 前清零（如vector<bool> visited(n, false)</bool>），不能只在函数内声明 - 每次递归入口处立刻判断
if (i = n || visited[i]) return;，否则可能越界访问或死循环 - 邻接表遍历时，对每个
neighbor都要先检查是否已访问，再递归——顺序不能颠倒
非递归 DFS：用 stack<int> 存节点索引，手动管理状态
用 stack 替代系统调用栈，能避免深递归导致的栈溢出，也方便在遍历中插入调试逻辑。但需注意：它不等价于“递归的逐行翻译”，而是按压栈顺序反向访问子节点。
- 压栈前就要标记
visited[node] = true，否则同一节点可能被多次压入 - 遍历邻接表时，推荐倒序压栈（如从
adj[node].rbegin()到rend()），使出栈顺序与递归一致 - 若需记录路径或深度，可在
stack中存pair<int, int>（节点 + 当前深度）
void dfs_iterative(int start, const vector<vector<int>>& adj) {
int n = adj.size();
vector<bool> visited(n, false);
stack<int> st;
st.push(start);
visited[start] = true;
while (!st.empty()) {
int u = st.top(); st.pop();
// 处理节点 u
for (auto it = adj[u].rbegin(); it != adj[u].rend(); ++it) {
int v = *it;
if (!visited[v]) {
visited[v] = true;
st.push(v);
}
}
}
}
DFS 回溯模板：用于排列、组合、棋盘问题等场景
这类 DFS 的核心不是遍历图，而是探索解空间树；必须配合「进入递归前 push/标记 → 递归返回后 pop/回退」的成对操作，否则状态污染。
立即学习“C++免费学习笔记（深入）”；
-
path和used是典型状态变量，每次修改都必须可逆 - 剪枝条件（如
if (path.size() == k)）应放在递归入口处，早停节省开销 - for 循环里从
start开始（组合）还是从0开始（排列），直接影响去重逻辑
图的连通性、拓扑排序、强连通分量这些进阶用途，都建立在基础 DFS 遍历正确性的前提上。最容易被忽略的是：递归版忘记传引用导致 visited 不生效，或者非递归版把 visited 标记位置错放到出栈后——这两个错误会让算法完全失效，且不易调试。
