C++实现DFS算法模板详解

递归DFS需初始化visited数组并在进入前检查越界和访问状态，非递归DFS用stack模拟并压栈前标记visited，回溯DFS须成对操作状态变量且剪枝前置。

直接用递归实现 DFS 最简洁，但要注意栈溢出和访问标记的时机；非递归版本用 stack 模拟更可控，适合图很大或深度不确定的场景。

递归 DFS：必须初始化 visited 数组并检查边界

递归写法最符合 DFS 直观逻辑，但容易漏掉两个关键点：一是未初始化 visited 数组导致重复访问，二是没在进入递归前检查索引越界或节点合法性。

• visited 必须在调用 DFS 前清零（如 vector visited(n, false)），不能只在函数内声明
• 每次递归入口处立刻判断 if (i < 0 || 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/回退」的成对操作，否则状态污染。

• path 和 used 是典型状态变量，每次修改都必须可逆
• 剪枝条件（如 if (path.size() == k)）应放在递归入口处，早停节省开销
• for 循环里从 start 开始（组合）还是从 0 开始（排列），直接影响去重逻辑

图的连通性、拓扑排序、强连通分量这些进阶用途，都建立在基础 DFS 遍历正确性的前提上。最容易被忽略的是：递归版忘记传引用导致 visited 不生效，或者非递归版把 visited 标记位置错放到出栈后——这两个错误会让算法完全失效，且不易调试。