c++中如何实现图的深度优先遍历_c++图DFS遍历方法

下次还敢

发布： 2025-10-16 13:15:01

原创

652人浏览过

C++中实现图的深度优先遍历需用邻接表存储图，通过递归或栈进行节点访问并标记已访问节点避免重复。1. 使用vector<vector<int>>表示邻接表；2. 递归实现DFS，从起始节点出发，访问未访问的邻接点并递归调用；3. 非递归实现使用stack模拟调用栈，压入起始节点后循环处理；4. 完整示例展示了从节点0开始的遍历过程，输出可能为0 1 3 2 4。若图非连通，需对每个未访问节点调用DFS。

c++中如何实现图的深度优先遍历_c++图dfs遍历方法

在C++中实现图的深度优先遍历（DFS），核心是使用递归或栈来访问每个顶点，并避免重复访问。通常结合邻接表存储图结构，再通过标记数组记录已访问节点。

1. 图的表示：邻接表

C++中常用vector的数组或vector的vector来表示邻接表。例如，用vector<int> graph[n] 表示n个顶点的无向图。

假设图有n个节点，编号从0到n-1，可以这样初始化：

vector<vector<int>> graph(n);
// 添加边 u - v
graph[u].push_back(v);
graph[v].push_back(u);

2. DFS递归实现

递归方式更直观，从起始节点开始，访问其所有未被访问的邻接点，并对每个邻接点递归调用DFS。

需要一个布尔数组visited[]来记录访问状态：

vector<bool> visited(n, false);

void dfs(int u) {
    visited[u] = true;
    cout << u << " ";

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

调用时指定起始节点，比如从节点0开始：

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

dfs(0);

3. 使用栈的非递归实现

若想避免递归带来的栈溢出风险（尤其在深层图中），可用STL中的stack模拟系统调用栈。

步骤如下：

豆绘AI

豆绘AI是国内领先的AI绘图与设计平台，支持照片、设计、绘画的一键生成。

485

查看详情

创建栈，压入起始节点
标记该节点为已访问
循环直到栈空：弹出一个节点并访问，将其所有未访问邻接点压栈并标记

void dfs_iterative(int start) {
    stack<int> st;
    st.push(start);
    vector<bool> visited(n, false);
    visited[start] = true;

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

        for (int v : graph[u]) {
            if (!visited[v]) {
                st.push(v);
                visited[v] = true;
            }
        }
    }
}

4. 完整示例代码

以下是一个完整可运行的DFS示例（递归版）：

include <iostream>

include <vector>

using namespace std;

vector<vector<int>> graph;
vector<bool> visited;

void dfs(int u) {
    visited[u] = true;
    cout << u << " ";
    for (int v : graph[u]) {
        if (!visited[v])
            dfs(v);
    }
}

int main() {
    int n = 5; // 节点数
    graph.resize(n);
    visited.assign(n, false);

    // 添加边
    graph[0].push_back(1);
    graph[1].push_back(0);
    graph[0].push_back(2);
    graph[2].push_back(0);
    graph[1].push_back(3);
    graph[3].push_back(1);
    graph[2].push_back(4);
    graph[4].push_back(2);

    cout << "DFS traversal: ";
    dfs(0);
    return 0;
}

输出结果为：0 1 3 2 4（具体顺序可能因邻接点插入顺序而异）

基本上就这些。根据实际需求选择递归或迭代方式，注意处理连通性问题——如果是非连通图，需对每个未访问节点都调用一次DFS。

以上就是c++++中如何实现图的深度优先遍历_c++图DFS遍历方法的详细内容，更多请关注php中文网其它相关文章！