Lesson 0408 · 图与图的遍历（BFS/DFS）

④ 数据结构与算法 — 第 8 课

1. 图是什么

图只有两个东西：

• 顶点（vertex，也叫节点 node）：一个「事物」，比如一座地铁站、一个人
• 边（edge）：两个顶点之间的关系，比如「这两站有直达」、「这两个人是好友」

一张图记作 G = (V, E)：V 是顶点集合，E 是边集合。就这么简单。

1.1 四种常见变体

1.2 几个必背的词

• 度（degree）：一个顶点连着几条边。有向图里分成入度（指向它的边数）和出度（从它出发的边数）
• 路径（path）：从 A 沿着边走到 B，经过的顶点序列
• 环（cycle）：一条路径能从某个点出发、绕一圈回到自己
• 连通块（连通分量）：互相能到达的一堆顶点，和外面完全断开

2. 图怎么存进电脑

图不是线性的，不能像数组那样一排就存好。有三种主流存法，各有各的适用场景。

2.1 邻接矩阵：开一个二维数组

int g[N][N];          // g[u][v] = 1 表示 u 到 v 有边

g[u][v] = 1;          // 加一条有向边 u -> v
g[v][u] = 1;          // 无向图再加这条（两个方向都能走）

if (g[u][v]) ...      // O(1) 判断 u、v 之间有没有边

• 优点：判断「两点之间有没有边」是 O(1)，写得最省脑子
• 缺点：空间 O(N²)。N = 1000 时是 100 万，还行；N = 100000 时是一百亿，直接爆内存
• 什么时候用：N ≤ 1000~2000，或者图非常稠密（边数接近 N²）

2.2 边表：把所有边列成一张表

vector<pair<int, int>> edges;     // 每条边存成一个 pair

edges.push_back({u, v});

• 优点：只看「有哪些边」时最方便（比如 Kruskal 最小生成树、Bellman-Ford 最短路）
• 缺点：想知道「u 的邻居有哪些」，得把整张表扫一遍

2.3 邻接表：本课主角

核心想法：对每个顶点，单独记一份「我的邻居名单」。

const int N = 100005;
vector<int> g[N];        // g[u] 里面装的是 u 的所有邻居

int main() {
    int n, m;
    cin >> n >> m;                       // n 个点，m 条边
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);                // 有向边 u -> v
        g[v].push_back(u);                // 无向图才要这一行！
    }
}

画出来就是「每个点背后挂一串邻居」：

1 -> [2, 3]
2 -> [1, 4, 5]
3 -> [1, 6, 7]
4 -> [2, 8]
5 -> [2, 8]
6 -> [3, 7]
7 -> [3, 6]
8 -> [4, 5]

• 空间：O(V + E) —— 每个点一个 vector，每条边存两次（无向图）
• 优点：快速枚举一个点的所有邻居，这是 DFS / BFS 最常做的事
• 缺点：判断「u、v 之间有没有边」要扫一遍 g[u]，O(度数)

3. 图的 DFS：比树的 DFS 多一个 visited

先回忆 0404 的树 DFS：从根出发，先钻左子树到底，再回来钻右子树。当时没有 visited，因为树没有环，顺着孩子走永远走不回来。

图不一样：1 → 2 → 3 → 1，这是个三角形。如果不标记走过的点，程序会 1 → 2 → 3 → 1 → 2 → 3 → … 一直转下去，直到栈溢出（RE），或者死循环超时（TLE）。

vector<bool> vis(n + 1, false);      // 注意是 n+1，因为顶点编号是 1..n

void dfs(int u) {
    vis[u] = true;                   // 一到就标记
    cout << u << " ";

    for (int v : g[u]) {             // 枚举 u 的所有邻居
        if (!vis[v]) dfs(v);         // 没走过的才进去
    }
}

用第 2.3 节那张图，从 1 号点出发，实际输出是：

DFS: 1 2 4 8 5 3 6 7

走的过程：1 → 2 → 4 → 8 →（8 的邻居都走过了）→ 退回 4 → 退回 2 → 5 →（都走过）→ 退回 1 → 3 → 6 → 7。这就是「一条路走到黑，走不通再退回来」。

3.1 图不连通怎么办

如果图分成了好几块，从 1 号点出发只能走完 1 所在的那一块。要遍历整张图，就在外面再套一层循环：

for (int i = 1; i <= n; i++) {
    if (!vis[i]) dfs(i);             // 每发现一个新连通块，就从它开始走
}

「外面套这一层循环，套了几次就有几个连通块」——这是数连通分量的标准写法（并查集能干同一件事，以后会学）。

3.2 复杂度

每个顶点最多被访问一次，每条边最多被看两次（无向图两个方向各一次）。所以：

邻接表 DFS = O(V + E)

4. 图的 BFS：用队列，一层一层往外扩

BFS 你已经很熟了（0405 的层序遍历就是）。图上唯一的改动还是 visited，而且标记的时机很关键。

void bfs(int s) {
    queue<int> q;
    q.push(s);
    vis[s] = true;                   // ★ 入队的时候就标记

    while (!q.empty()) {
        int u = q.front();
        q.pop();
        cout << u << " ";

        for (int v : g[u]) {
            if (!vis[v]) {
                vis[v] = true;       // ★ 在这里标，不是出队时标
                q.push(v);
            }
        }
    }
}

同一张图，BFS 输出：

BFS: 1 2 3 4 5 6 7 8

1 是第一层，2 和 3 是第二层，4、5、6、7 是第三层，8 是第四层——整齐地按距离分层。这正是 BFS 最值钱的性质。

5. 手推：同一张图，队列和栈各走一遍

就用 2.3 节那张 8 个点的图，从 1 号点出发。邻居的枚举顺序按名单从左到右，这样推出来的结果正好是上面那两个输出。

5.1 BFS：队列里有什么，按层展开

盯住「队列」那一列：每个点最多出现一次。这就是「入队时标记」的直接效果——如果等出队再标记，4 会在第 2 步和第 3 步各被塞进去一次。

5.2 DFS：栈里是「当前这条路径」

第 5 步最容易看晕：8 的邻居名单是 [4, 5]，4 刚走过，所以 5 是「从 8 进去的」，栈里 4 和 8 都还在（1 2 4 8 5）。等 5 也走完（邻居 2、8 全访问过），栈才一路退回 2、再退回 1，然后才轮到 1 的第二个邻居 3。这就是 DFS 的实质：栈里永远只有当前这条路径。

访问顺序 1 2 4 8 5 3 6 7 和 3 节打印的 DFS 结果一致；BFS 的 1 2 3 4 5 6 7 8 也和 4 节一致。自己拿张纸把两张表盖住重推一遍，图就真的进脑子里了。

6. DFS 和 BFS 到底怎么选

7. 例题思路：P5318 查找文献

题意：n 个点、m 条有向边（文献引用关系），从 1 号点出发，输出 DFS 序和 BFS 序；同一层的点，编号小的先访问。

三个关键点：

1. 有向图 —— 只写 g[u].push_back(v)，千万别加反向边
2. 「编号小的先访问」 —— 邻接表里邻居的顺序是输入顺序，是乱的。先给每份名单排个序：

for (int i = 1; i <= n; i++) {
    sort(g[i].begin(), g[i].end());   // 保证枚举邻居时从小到大
}

3. 两次遍历要两个 vis 数组，或者遍历完 DFS 之后把 vis 清空再 BFS。用 vis.assign(n+1, false) 最省事。

所以整题的形状是：读边 → 给每个 g[i] 排序 → 跑一遍 DFS 输出一行 → 清空 vis → 跑一遍 BFS 输出一行。

复杂度：排序 O(V log V)，遍历 O(V + E)，合起来完全够用。

8. 网格图：把坐标当成点

迷宫、棋盘这类题，图上没有「1 号点、2 号点」，只有格子。这时候把每个格子 (x, y) 看成一个顶点：

• 顶点 = 一个格子
• 边 = 从这个格子能走到相邻格子（上下左右，或马的八个方向）

既然点变成了坐标，就不开 g[] 了，直接用方向数组现场算邻居：

int dx[4] = {-1, 1, 0, 0};        // 上 下 左 右
int dy[4] = {0, 0, -1, 1};

for (int k = 0; k < 4; k++) {
    int nx = x + dx[k];
    int ny = y + dy[k];

    if (nx < 1 || nx > n || ny < 1 || ny > m) continue;   // 越界
    if (a[nx][ny] == 1) continue;                          // 障碍/不能走
    if (vis[nx][ny]) continue;                             // 走过

    // 接下来对 (nx, ny) 做事
}

这套骨架，迷宫、岛屿数量、连通块计数、洪水填充……都长这样。换的只是「能不能走」的判断条件。

8.1 P1605 迷宫：DFS + 回溯

这题问的是「从起点到终点一共有多少条路径」。

注意 DFS 在这题的写法有个新动作：走完一条路之后，要把标记撤销。因为你要找的是所有路径，走过的那格在「下一条路线」里还得允许再走。

void dfs(int x, int y) {
    if (x == fx && y == fy) {
        ans++;                      // 到达终点，路径数 +1
        return;
    }
    for (int k = 0; k < 4; k++) {
        int nx = x + dx[k], ny = y + dy[k];
        if (nx < 1 || nx > n || ny < 1 || ny > m) continue;
        if (a[nx][ny] == 1 || vis[nx][ny]) continue;

        vis[nx][ny] = true;         // 标记：这一步走过了
        dfs(nx, ny);
        vis[nx][ny] = false;        // ★ 撤销：回溯的灵魂，别忘了
    }
}

8.2 P1443 马的遍历：BFS 求最短步数

「从起点骑马到每个格子最少几步」——看到「最少步数」，条件反射就该想到 BFS。

做法：用 d[x][y] 存步数，初始全为 -1（顺便当 visited 用，-1 表示没到过）。

int dx[8] = {-2, -1, 1, 2, 2, 1, -1, -2};    // 马走"日"字
int dy[8] = {1, 2, 2, 1, -1, -2, -2, -1};

vector<vector<int>> d(n + 1, vector<int>(m + 1, -1));
queue<pair<int, int>> q;

q.push({sx, sy});
d[sx][sy] = 0;

while (!q.empty()) {
    auto [x, y] = q.front();
    q.pop();

    for (int k = 0; k < 8; k++) {
        int nx = x + dx[k], ny = y + dy[k];
        if (nx < 1 || nx > n || ny < 1 || ny > m) continue;
        if (d[nx][ny] != -1) continue;        // 到过就别再入队

        d[nx][ny] = d[x][y] + 1;              // 步数 = 上一格 + 1
        q.push({nx, ny});
    }
}

实际跑一张 5×5 的棋盘（从 (1,1) 出发），得到：

0 3 2 3 2
3 4 1 2 3
2 1 4 3 2
3 2 3 2 3
2 3 2 3 4

注意 -1 的格子表示「永远到不了」。输出格式要求每个数占 5 个字符宽度左对齐，用：

cout << setw(5) << left << d[i][j];

（setw 来自 <iomanip>，你在 P1157 用过 setw(3)。）

9. 复杂度小结

1e5 个点、2e5 条边 → 邻接表毫无压力；邻接矩阵会开出几百 G 的内存，直接爆。

10. 坑点清单

• 忘了 visited → 有环就死循环 / RE。图上的 DFS、BFS 都必须有
• 有向、无向搞混 → 无向图漏加反向边；有向图多加反向边（P5318 有向，务必只加一条）
• BFS 出队时才标记 → 重复入队，时间退化，大数据 TLE
• vis 开成 n 而不是 n + 1 → 顶点编号 1..n，vis[n] 越界；两次遍历共用 vis 没清空，第二次什么都输出不了
• 递归太深 → 链状图 1e5 个点，递归 DFS 可能爆栈。改成 BFS 或自己用 stack
• 网格题的三个常见小错 → 下标 0 和 1 混用（建议统一从 1 开始，开 (n+2) × (m+2)）；P1605 忘记撤销 vis，路径数偏小；二维 vector 忘了第二个参数，d(n+1, vector<int>(m+1, -1))

11. 小测

12. 动手练习

按顺序做，一题一题来。第一题把存图 + 遍历跑通，后两题把两种思路分别练到手熟。

1. P5318 查找文献 —— 邻接表 + DFS + BFS + 给邻居排序。有向图，别加反向边。做完就说明「图的基本功」过关了
2. P1605 迷宫 —— 网格 DFS + 回溯。重点体会「标记 / 撤销」成对写
3. P1443 马的遍历 —— 网格 BFS 求最短步数。重点练方向数组和「步数数组兼当 visited」

做不出来时的自查顺序

1. 图存对了吗？有向只加一条边，无向要加两条，N 开够大。
2. vis 开的是 n + 1 吗？顶点编号是 1..n。
3. BFS 的标记是不是写在入队那一步？出队才标记就会重复入队。
4. 拿第 5 节那两张表手推一遍，把队列 / 栈里的内容写在纸上，和表对。
5. 网格题：方向数组的越界判断写全了吗？P1605 有没有成对撤销？
6. 还是不行就把代码贴过来，我们一起看。

本课小结

• 图 = 顶点 + 边；有向 / 无向、带权 / 不带权，是最主要的两种划分方式
• 邻接表 vector<int> g[N] 是默认选择，空间和遍历都是 O(V + E)
• 图上 DFS / BFS 与树的版本只差一个 visited；DFS 钻到底，BFS 一层层扩
• BFS 的标记必须在入队时；只有 BFS 能求无权图的最短步数
• 网格图 = 顶点是坐标的图，用方向数组现场算邻居
• 求「路径条数」要 DFS + 回溯，标记和撤销成对写
• 邻接矩阵只在 V 很小或要 O(1) 查边时才用