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

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

冰火之心

发布： 2025-11-21 19:29:06

原创

776人浏览过

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

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

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

递归实现DFS

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

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

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

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

    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: ";
    dfs_recursive(1);
    cout << endl;
    return 0;
}

非递归实现DFS

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

AssemblyAI

转录和理解语音的AI模型

查看详情

#include <stack>

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

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

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

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