c++怎么实现图的深度优先搜索(DFS)_c++图遍历DFS算法实现-C++-PHP中文网

c++怎么实现图的深度优先搜索(DFS)_c++图遍历DFS算法实现

尼克

发布： 2025-10-22 13:36:01

原创

855人浏览过

图的深度优先搜索从起始顶点开始沿路径深入访问，使用邻接表和递归或栈实现；需标记访问状态避免重复，对不连通图需多次调用DFS以遍历所有节点。

c++怎么实现图的深度优先搜索(dfs)_c++图遍历dfs算法实现

图的深度优先搜索（DFS）是一种用于遍历或搜索图中节点的算法。它从一个起始顶点开始，沿着一条路径尽可能深入地访问未访问过的邻接点，直到无法继续前进，再回溯并尝试其他分支。C++ 中可以通过邻接表或邻接矩阵结合递归或栈来实现 DFS。

使用邻接表和递归实现 DFS

邻接表是表示图的一种高效方式，尤其适用于稀疏图。使用 vector<vector<int>> 存储每个顶点的邻接点，配合布尔数组记录访问状态。

步骤说明：

创建图的邻接表结构
维护一个 visited 数组防止重复访问
从指定起点开始递归访问所有未访问的邻接点

代码示例：

立即学习“C++免费学习笔记（深入）”；

#include <iostream>
#include <vector>
using namespace std;

class Graph {
    int V; // 顶点数量
    vector<vector<int>> adj; // 邻接表

    void dfsUtil(int v, vector<bool>& visted) {
        visted[v] = true;
        cout << v << " ";

        for (int neighbor : adj[v]) {
            if (!visted[neighbor]) {
                dfsUtil(neighbor, visted);
            }
        }
    }

public:
    Graph(int V) {
        this->V = V;
        adj.resize(V);
    }

    void addEdge(int u, int v) {
        adj[u].push_back(v);
        adj[v].push_back(u); // 无向图，若为有向图则删除此行
    }

    void dfs(int start) {
        vector<bool> visited(V, false);
        dfsUtil(start, visited);
    }
};

// 使用示例
int main() {
    Graph g(5);
    g.addEdge(0, 1);
    g.addEdge(0, 2);
    g.addEdge(1, 3);
    g.addEdge(2, 4);

    cout << "从顶点 0 开始的 DFS 遍历: ";
    g.dfs(0);
    return 0;
}

登录后复制

使用栈实现非递归 DFS

递归本质是系统调用栈，也可以手动使用 stack 实现 DFS，避免递归带来的栈溢出风险，尤其在图较大时更安全。

纳米搜索

纳米搜索：360推出的新一代AI搜索引擎

查看详情

核心思路：

用 stack 存储待访问的顶点
每次取出栈顶，标记为已访问并输出
将其未访问的邻接点压入栈

非递归实现代码片段：

void dfsIterative(int start) {
    vector<bool> visited(V, false);
    stack<int> stk;
    stk.push(start);

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

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

        // 逆序压入邻接点，保证顺序一致（可选）
        for (auto it = adj[curr].rbegin(); it != adj[curr].rend(); ++it) {
            if (!visited[*it]) {
                stk.push(*it);
            }
        }
    }
}

登录后复制