c++中如何实现深度优先搜索DFS_c++ DFS算法模板

穿越時空 2026-01-06 00:00:00 次阅读

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

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

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

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

visited 必须在调用 DFS 前清零（如 vector visited(n, false)），不能只在函数内声明
每次递归入口处立刻判断 if (i = n || visited[i]) return;，否则可能越界访问或死循环
邻接表遍历时，对每个 neighbor 都要先检查是否已访问，再递归——顺序不能颠倒

非递归 DFS：用 stack 存节点索引，手动管理状态

用 stack 替代系统调用栈，能避免深递归导致的栈溢出，也方便在遍历中插入调试逻辑。但需注意：它不等价于“递归的逐行翻译”，而是按压栈顺序反向访问子节点。

压栈前就要标记 visited[node] = true，否则同一节点可能被多次压入
遍历邻接表时，推荐倒序压栈（如从 adj[node].rbegin() 到 rend()），使出栈顺序与递归一致
若需记录路径或深度，可在 stack 中存 pair（节点 + 当前深度）

void dfs_iterative(int start, const vector>& adj) {
    int n = adj.size();
    vector visited(n, false);
    stack 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);
            }
        }
    }
}