C++如何实现图的深度优先搜索（DFS）？（代码示例）

穿越時空 2025-12-22 00:00:00 次阅读

C++实现图的DFS核心是递归或栈模拟回溯，需标记已访问节点防重复；邻接表为首选存储结构，递归版简洁直观，非递归版避免栈溢出，连通分量需遍历所有未访问顶点启动DFS。

用C++实现图的DFS，核心是递归或栈模拟回溯过程，关键在于标记已访问节点、避免重复遍历。邻接表是最常用且高效的存储方式。

用邻接表 + 递归实现DFS

适合大多数场景，代码简洁，逻辑直观。假设图是无向图，顶点编号从0开始：

#include 
#include 
using namespace std;

void dfs(int u, vector& visited, const vector>& graph) {
    visited[u] = true;
    cout << u << " ";  // 访问操作（可替换为其他处理）

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

int main() {
    int n = 6;  // 顶点数
    vectorector> graph(n);
    // 添加边：0-1, 0-2, 1-3, 1-4, 2-5
    graph[0] = {1, 2};
    graph[1] = {0, 3, 4};
    graph[2] = {0, 5};
    graph[3] = {1};
    graph[4] = {1};
    graph[5] = {2};

    vector visited(n, false);
    cout << "DFS遍历顺序: ";
    dfs(0, visited, graph);  // 从顶点0开始
    cout << endl;
    return 0;
}

用栈实现非递归DFS

避免递归调用栈溢出，更适合大规模图或深度受限环境：

#include 
#include 
#include 
using namespace std;

void dfs_iterative(int start, const vector>& graph) {
    int n = graph.size();
    vector visited(n, false);
    stack st;
    
    st.push(start);
    visited[start] = true;
    cout << start << " ";

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

        // 注意：这里要倒序遍历邻接点，才能和递归版顺序一致（可选）
        for (auto it = graph[u].rbegin(); it != graph[u].rend(); ++it) {
            int v = *it;
            if (!visited[v]) {
                visited[v] = true;
                cout << v << " ";
                st.push(v);
            }
        }
    }
}