c++怎么实现深度优先搜索（DFS）_c++中DFS算法的递归与非递归实现

穿越時空 2025-11-04 00:00:00 次阅读

深度优先搜索（DFS）可通过递归和非递归实现。递归法利用函数调用栈，代码简洁；非递归法使用显式栈避免栈溢出，适合深度大的图。两者时间复杂度均为O(V+E)，空间复杂度O(V)。

深度优先搜索（DFS）是一种用于遍历或搜索图或树的算法。在C++中，DFS可以通过递归和非递归两种方式实现。下面分别介绍这两种方法，并给出具体代码示例。

递归实现DFS

递归是最直观、最常用的DFS实现方式。它利用函数调用栈自动保存访问路径。

思路： 从起始节点开始，标记为已访问，然后对每个未访问的邻接节点递归调用DFS。

使用一个布尔数组记录节点是否被访问过
用邻接表存储图结构（如vector>）
递归进入每一个未访问的相邻节点

代码示例：

#include 
#include 
using namespace std;

void dfs_recursive(const vector>& graph, vector& visited, int node) {
    visited[node] = true;
    cout << node << " ";

    for (int neighbor : graph[node]) {
        if (!visited[neighbor]) {
            dfs_recursive(graph, visited, neighbor);
        }
    }
}

int main() {
    int n = 5; // 节点数
    vector> graph(n);
    vector visited(n, false);

    // 构建图：0-1, 0-2, 1-3, 1-4
    graph[0] = {1, 2};
    graph[1] = {3, 4};
    graph[2] = {};
    graph[3] = {};
    graph[4] = {};

    cout << "递归DFS: ";
    dfs_recursive(graph, visited, 0);
    cout << endl;

    return 0;
}

非递归实现DFS

非递归版本使用显式的栈（stack）来模拟函数调用过程，避免递归带来的栈溢出风险，尤其适用于深度很大的图。

思路： 使用STL中的stack保存待访问的节点。每次取出栈顶，标记访问，并将其未访问的邻居压入栈中。

手动维护一个栈结构
先访问当前节点，再将邻居逆序入栈（保证顺序一致）
注意入栈前判断是否已访问，避免重复处理

代码示例：

#include 
#include 
#include 
using namespace std;

void dfs_iterative(const vector>& graph, int start) {
    int n = graph.size();
    vector visited(n, false);
    stack stk;

    stk.push(start);

    while (!stk.empty()) {
        int node = stk.top();
        stk.pop();

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

        // 逆序压入邻居，确保先访问编号小的节点
        for (auto it = graph[node].rbegin(); it != graph[node].rend(); ++it) {
            if (!visited[*it]) {
                stk.push(*it);
            }
        }
    }
}

int main() {
    int n = 5;
    vector> graph(n);

    graph[0] = {1, 2};
    graph[1] = {3, 4};
    graph[2] = {};
    graph[3] = {};
    graph[4] = {};

    cout << "非递归DFS: ";
    dfs_iterative(graph, 0);
    cout << endl;

    return 0;
}