C++如何实现深度优先搜索(DFS)_C++图论算法中DFS的递归与非递归写法

深度优先搜索（DFS）可通过递归和非递归实现，递归写法简洁但可能栈溢出，非递归用显式栈更安全；1. 递归实现利用函数调用栈自动管理路径，代码清晰；2. 非递归使用stack模拟，需逆序压入邻接点以保证输出一致；3. 访问标记在节点首次访问时设置，防止重复入栈；4. 对于非连通图需多次启动DFS；5. 两种方法均适用于邻接表存储的无向图，扩展后可处理带权图。掌握二者可应对多数图遍历场景。

深度优先搜索（DFS）是图论中一种基础且重要的遍历算法，广泛应用于连通性判断、路径查找、拓扑排序等问题。在C++中，DFS可以通过递归和非递归两种方式实现。下面分别介绍这两种写法，并结合邻接表存储的无向图进行说明。

递归实现DFS

递归写法简洁直观，利用函数调用栈自动管理访问路径。

// 使用邻接表表示图
#include
#include iostream>
using namespace std;

// 全局变量：图的邻接表、访问标记数组
vector> graph;
vector visited;

void dfs_recursive(int u) {
    visited[u] = true;
    cout   // 输出当前节点

    for (int v : graph[u]) {
        if (!visited[v]) {
            dfs_recursive(v);
        }
    }
}

// 初始化图并调用DFS
int main() {
    int n = 5; // 节点数
    graph.resize(n + 1);
    visited.assign(n + 1, false);

    // 构建无向图
    graph[1].push_back(2); graph[2].push_back(1);
    graph[1].push_back(3); graph[3].push_back(1);
    graph[2].push_back(4); graph[4].push_back(2);
    graph[2].push_back(5); graph[5].push_back(2);

    cout
    dfs_recursive(1);
    cout
    return 0;
}

非递归实现DFS

非递归使用显式栈（stack）模拟系统调用栈，避免递归带来的栈溢出风险，适合大规模图。

#include

void dfs_iterative(int start) {
    stack st;
    st.push(start);

    while (!st.empty()) {
        int u = st.top();
        st.pop();

        if (visited[u]) continue;
        visited[u] = true;
        cout

        // 将邻接节点压入栈（逆序保证顺序一致）
        for (auto it = graph[u].rbegin(); it != graph[u].rend(); ++it) {
            if (!visited[*it]) {
                st.push(*it);
            }
        }
    }
}

两种写法对比与注意事项

递归写法代码短，逻辑清晰，但深层图可能引发栈溢出；非递归写法控制力更强，适用于生产环境或大图处理。

• 访问标记应在节点弹出时立即设置，防止重复入栈
• 非递归中逆序遍历邻接表可使输出顺序与递归一致
• 若图不连通，需对每个未访问节点启动一次DFS
• 边权图可在结构体中扩展信息，如pair或自定义Node

基本上就这些。掌握这两种写法能应对大多数图遍历问题。