c++怎么实现深度优先搜索dfs_c++ 图的邻接表表示与递归遍历【案例】

尼克

发布时间：2026-01-07 18:40:02

284人浏览过

来源于php中文网

原创

邻接表用vector构建，外层索引为顶点编号，内层存邻居；无向图双向加边，有向图单向加边；DFS递归需含当前节点、visited数组和邻接表，缺visited将导致无限递归。

c++怎么实现深度优先搜索dfs_c++ 图的邻接表表示与递归遍历【案例】

邻接表怎么建：用 `vector>` 最直接

图的邻接表本质是每个节点维护一个邻居列表。C++ 中最常用、最轻量的方式是 vector>，外层索引代表顶点编号（0-based 或 1-based），内层 vector 存所有邻接点。

注意点：

如果顶点数已知（比如 n 个），初始化时就预留空间：vector> graph(n);
无向图要双向加边：graph[u].push_back(v); graph[v].push_back(u);
有向图只加单向：graph[u].push_back(v);
避免重复建边（除非题目允许重边），否则 DFS 可能误入环或多次访问同一节点

DFS 递归函数怎么写：三个核心要素缺一不可

标准 DFS 递归实现必须包含：当前节点、访问标记数组、邻接表。漏掉 visited 就会无限递归（尤其在有环图中）。

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);
        }
    }
}

常见错误：

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

腾讯云AI代码助手

基于混元代码大模型的AI辅助编码工具

下载

忘记传 visited 引用，导致每次递归都是副本，标记无效
把 visited 声明在函数内部，每次调用都重置
没检查 v 是否越界（尤其当邻接表里存了非法索引时）

从哪个点开始遍历：别默认只跑 `dfs(0)`

图不一定是连通的。只调用一次 dfs(0) 只能访问到 0 所在的连通分量。要遍历全图，必须对每个未访问节点启动 DFS：

vector visited(n, false);
for (int i = 0; i < n; ++i) {
    if (!visited[i]) {
        dfs(i, visited, graph);
        // 这里可加换行或分隔符，表示一个新连通分量
        cout << "\n";
    }
}

典型场景：

求连通分量个数 → 统计外层循环中进入 dfs 的次数
判断图是否连通 → 看最终 visited 是否全为 true
重建森林结构 → 每次进入 dfs 对应一棵生成树的根

想记录路径或回溯怎么办：加参数 + 回退操作

如果需要输出某条从起点到终点的路径，或做路径相关决策（如找最短路、判断是否存在某约束路径），就得把当前路径存下来，并在递归返回时弹出栈顶：

void dfs_path(int u, int target, vector& visited,
               vector& path, const vector>& graph) {
    visited[u] = true;
    path.push_back(u);
    if (u == target) {
        // 找到目标，可打印或保存 path
        for (int x : path) cout << x << " ";
        cout << "\n";
    } else {
        for (int v : graph[u]) {
            if (!visited[v]) {
                dfs_path(v, target, visited, path, graph);
            }
        }
    }
    path.pop_back(); // 关键：回溯，恢复现场
    visited[u] = false; // 若允许多次经过同一节点（如带权图枚举所有路径），需取消注释
}

容易被忽略的细节：