C++图的DFS遍历

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

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

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

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

图由两部分组成：

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

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

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

画出来就是：

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

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

想象你要从教学楼（0）出发，访问学校里所有能走到的建筑。你会怎么做？

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

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

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

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

用代码实现 DFS

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

下面是完整的代码框架（后面会给出完整可运行的示例）：

#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 条边（无向图）：

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

手动模拟 DFS 过程

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

输出顺序：0 1 3 4 2

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

新手容易犯的错误

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

完整可运行的代码示例

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

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

输入示例（非连通图，包含一个孤立顶点）：

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

输出示例：

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

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