困难C++8 分钟2,858 字

C++图的DFS遍历

C++中图的深度优先遍历(DFS)——像走迷宫一样探索图

在学习图的时候,我们经常需要“走遍”图中所有的顶点,就像你想认识一座新城市里所有有趣的地方一样。​DFS(深度优先搜索)​ 就是一种非常直观的遍历方法:选定一个起点,然后沿着一条路一直往前走,直到走不动了(没有未访问的邻居),再退回上一个岔路口,换另一条路继续走。这个过程很像在迷宫中探险——先一条道走到黑,不行就回头。

DFS 在编程里通常用递归​来实现,因为它能自动帮我们记住走过的路径。下面我们就一步步拆解这个“迷宫探险”的过程。


什么是图?用生活例子来理解

图由两部分组成:

  • 顶点​​:图中的“点”,可以想象成城市、手机用户、游戏里的关卡。
  • 边​:连接两个顶点的“线”,表示它们之间有直接关系,比如城市之间的道路、朋友关系、关卡之间的通道。

比如,你有一张学校地图:教学楼(顶点0)、食堂(顶点1)、操场(顶点2)、图书馆(顶点3)、宿舍(顶点4)。几条路连接它们:

  • 教学楼 ↔ 食堂
  • 教学楼 ↔ 操场
  • 食堂 ↔ 图书馆
  • 食堂 ↔ 宿舍

画出来就是:

    0——1
    |   |
    2   3
        |
        4

这就是一张无向图​​(边没有方向,可以来回走)。如果道路是单向的(比如只能从教学楼到食堂,不能反过来),那就是有向图​​。今天我们学的 DFS 对两种图都适用,只是要注意方向。


DFS 的核心思想:一条路走到底

想象你要从教学楼(0)出发,访问学校里所有能走到的建筑。你会怎么做?

  • 先走到食堂(1),因为它是教学楼最近的邻居之一。
  • 到了食堂,你看到前面还有路通向图书馆(3)和宿舍(4),你选择先走图书馆那条路。
  • 从图书馆继续走,发现没有其他路可走了,于是你退回食堂,再去宿舍。
  • 宿舍也没有新路,退回食堂,食堂也没有新路,再退回教学楼,然后去操场(2)。
  • 操场也没有新路,好了,所有能到的地方都走完了。

这个过程就是 DFS:​深度优先​​,意思是尽可能往深处走,走到底再回头。它与宽度优先(BFS)​ 不同,BFS 是一层一层地走,像水波扩散。

为什么需要“标记访问”?

如果走过的地方不记住,你可能会在食堂和图书馆之间反复乱转,陷入死循环。所以我们需要一个visited 数组​​,像一张“已打卡”清单,记录每个顶点是否已经去过。


用代码实现 DFS

我们使用邻接表​来存储图。邻接表就是为每个顶点准备一个“邻居列表”,里面存着所有与它直接相连的顶点。比如教学楼(0)的邻居列表是 [1, 2](食堂和操场)。

下面是完整的代码框架(后面会给出完整可运行的示例):

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

const int MAXN = 100;           // 最大顶点数
vector<int> graph[MAXN];        // 邻接表:graph[0] 存顶点0的所有邻居
bool visited[MAXN];             // visited[i] 为 true 表示顶点 i 已访问过

// DFS函数:从顶点 u 开始探索
void dfs(int u) {
    visited[u] = true;          // 标记当前顶点为已访问
    cout << u << " ";           // 输出当前顶点(表示“打卡”)

    // 遍历 u 的每一个邻居 v
    for (int v : graph[u]) {
        if (!visited[v]) {      // 如果邻居 v 还没有去过
            dfs(v);             // 递归去 v 继续探索
        }
    }
    // 所有邻居都处理完,函数自动返回,相当于“退回上一个岔路口”
}

代码解释​​:

  • graph[u] 是一个 vector<int>,里面放着所有与 u 相连的顶点编号。
  • visited[u] = true; 一进函数就标记,防止重复走。
  • for (int v : graph[u]) 遍历所有邻居。如果邻居没去过,就递归调用 dfs(v)。
  • 当 for 循环结束(所有邻居都处理完),函数自然结束,回到上一层调用处——这就是“回头”。

完整示例:一步步演示

假设我们有 5 个顶点(编号 0~4),4 条边(无向图):

5 4
0 1
0 2
1 3
1 4

图的结构就是刚才学校例子。从顶点 0 开始 DFS。

手动模拟 DFS 过程

  1. 调用 dfs(0)
  • 标记 visited[0]=true,输出 0。
  • 邻居列表 [1, 2]。先看 1:未访问 → 调用 dfs(1)。
  1. 进入 dfs(1)
  • 标记 visited[1]=true,输出 1。
  • 邻居列表 [0, 3, 4]。0 已访问,跳过;看 3:未访问 → 调用 dfs(3)。
  1. 进入 dfs(3)
  • 标记 visited[3]=true,输出 3。
  • 邻居列表 [1]。1 已访问,没有未访问邻居 → 返回。
  1. 回到 dfs(1) 继续执行 for 循环的下一个邻居:4。
  • 4 未访问 → 调用 dfs(4)。
  1. 进入 dfs(4)
  • 标记 visited[4]=true,输出 4。
  • 邻居列表 [1]。1 已访问 → 返回。
  1. **回到 dfs(1)**​​,所有邻居处理完 → 返回。
  2. **回到 dfs(0)**​​,继续处理下一个邻居:2。
  • 2 未访问 → 调用 dfs(2)。
  1. 进入 dfs(2)
  • 标记 visited[2]=true,输出 2。
  • 邻居列表 [0]。0 已访问 → 返回。
  1. **回到 dfs(0)**​​,所有邻居处理完 → 整个 DFS 结束。

输出顺序​​:0 1 3 4 2

你可以发现,DFS 总是先深入一条支路(0→1→3),然后回头走另一条支路(1→4),再回头走最后一条(0→2)。


新手容易犯的错误

  1. 忘记标记 visited 如果没有 visited[u] = true;,递归会反复进入同一个顶点,导致栈溢出(程序崩溃)或无限循环。 ✅ 结论:​​进入函数第一件事就是标记自己已访问​。
  2. 只遍历一个连通分量 如果图不是连通图(比如有的顶点孤零零,和起点没有路径),从单个起点出发的 DFS 只能访问到起点所在的“那块”图。例如上面的例子,如果还有一个顶点 5 没有边连到 0~4,DFS(0) 就不会访问到 5。 ✅ 解决方法:遍历所有顶点,对每个未访问的顶点都调用一次 dfs。 for (int i = 0; i < n; i++) { if (!visited[i]) dfs(i); }
  3. 递归层次太深导致栈溢出 如果图的顶点特别多(比如 10 万),递归调用可能会超出函数调用栈的限制。这时可以考虑用​显式栈代替递归(但初学者先掌握递归版即可)。 ✅ 小提示:大部分题目中 n ≤ 10000 时递归都没问题。
  4. 邻接表忘记添加双向边 对于无向图,一条边 u-v 需要在 graph[u] 和 graph[v] 中都添加对方。很多新手只加了 graph[u].push_back(v),结果从 v 出发找不到 u,遍历不完整。

完整可运行的代码示例

下面是一个完整的程序,从标准输入读入图,然后从顶点 0 开始 DFS,并输出访问顺序。同时,为了处理非连通图,我们还对每个未访问顶点都启动一次 DFS。

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

const int MAXN = 1000;          // 最大顶点数,可根据需要调整
vector<int> graph[MAXN];        // 邻接表
bool visited[MAXN];             // 标记是否访问过

// 深度优先搜索函数
void dfs(int u) {
    visited[u] = true;          // 标记为已访问
    cout << u << " ";           // 输出当前顶点

    // 遍历所有与 u 相连的顶点 v
    for (int v : graph[u]) {
        if (!visited[v]) {      // 如果 v 没去过
            dfs(v);             // 递归访问 v
        }
    }
}

int main() {
    int n, m;                   // n: 顶点个数,m: 边数
    cin >> n >> m;

    // 读入 m 条边(无向图)
    for (int i = 0; i < m; i++) {
        int u, v;               // 一条边的两个端点
        cin >> u >> v;
        graph[u].push_back(v);  // u 的邻居加 v
        graph[v].push_back(u);  // v 的邻居加 u(无向图要双向添加)
    }

    // 对每个未访问的顶点启动 DFS(处理非连通图)
    for (int i = 0; i < n; i++) {
        if (!visited[i]) {
            cout << "从顶点 " << i << " 开始 DFS: ";
            dfs(i);
            cout << endl;
        }
    }

    return 0;
}

输入示例​​(非连通图,包含一个孤立顶点):

6 4
0 1
0 2
1 3
1 4

顶点 5 没有边,是孤立的。

输出示例​​:

从顶点 0 开始 DFS: 0 1 3 4 2
从顶点 5 开始 DFS: 5

这样我们就访问到了所有顶点。


相关指引

掌握了 DFS 之后,你可以继续学习:

  • 广度优先搜索(BFS)​​​:适合求最短路径、层级遍历等问题。
  • 连通分量​​:利用 DFS 可以轻松找出图中所有连通的部分(上面的代码已经做到了)。
  • 拓扑排序​​:在有向无环图中,DFS 可以用于确定任务执行的先后顺序。
  • 检测环​​:DFS 可以判断图中是否存在环(比如在朋友关系中看有没有循环引用)。
  • 欧拉路径​​:一笔画问题,也用到了 DFS 的思想。

DFS 是图论中最基础、最强大的工具之一,学会它之后,很多问题都会迎刃而解。快打开你的 IDE,亲手跑一跑上面的代码,体会一下“一条路走到黑”的探险乐趣吧!

同类知识点