InoueMoby's Blog

前言

你站在一座城市的某个路口，想走遍所有街道。有两种策略：一是”一条路走到黑，走不通再回头”——就像走迷宫时总是沿右手墙壁前进，直到撞墙才换方向。这就是深度优先搜索（DFS）。二是”先逛完附近的所有路口，再向外扩展”——就像水波纹一样，从中心一圈圈向外扩散。这就是广度优先搜索（BFS）。

这两种策略看似简单，却是整个图论的根基。最短路、拓扑排序、连通性判断、环检测……全都建立在遍历之上。后面七篇图论文章里的每一个算法，本质上都是 DFS 或 BFS 的变体——“加点料”而已。

但遍历有一个前提：先把图存到计算机里。教材（Tessoku Book 9.1 B61 Influencer）用”友達関係”（朋友关系）来引入图的邻接表存储。这一节我们从”图长什么样、怎么存”说起，然后分别讲解 DFS 和 BFS 的原理。

问题的本质

图是什么？怎么存？

想象你在看一张地铁线路图。每个站是一个顶点（vertex），两站之间的连线是一条边（edge）。边可以有方向（单行道），也可以有权重（站间距）。

竞赛中图以”边列表”的形式给出： $N$ 个顶点、 $M$ 条边，每条边连接 $A_i$ 和 $B_i$ 。你的任务是从这堆边里还原出整张图的结构。

怎么存？ 最直觉的想法是二维数组 G[i][j] 表示 $i$ 到 $j$ 是否有边——这就是邻接矩阵。但 $N = 10^5$ 时矩阵要 $10^{10}$ 个元素，直接爆内存。而且大部分格子都是 0（稀疏图），浪费严重。

竞赛中几乎总是用邻接表：每个顶点维护一个列表，只存它的邻居。教材 B61 的实现就是 vector<int> G[100009]，空间 $O(N+M)$ ，遍历邻居时只看真正存在的边。

教材还指出了一个实用性质：邻接表中 G[i].size() 就是顶点 $i$ 的次数（degree）——有多少条边连着它。B61 的问题正是求次数最大的顶点。

DFS：为什么”走到黑”不会漏掉节点？

DFS 的策略是：到了一个新节点，随便挑一个没走过的邻居继续走。走到死路（所有邻居都走过了）就原路返回，回到上一个还有未走邻居的岔路口，换一条路继续。

为什么这样一定能走遍所有节点？ 因为图是连通的（任意两点之间有路径）。从起点出发，每条边最多被走过两次（正向一次、回溯时不走）。回溯保证了你不会”卡在”某条路径上——总能退回到岔路口换路。

为什么需要 visited 数组？ 想象图是一个三角形（1-2-3-1）。从 1 出发走到 2，2 的邻居是 1 和 3。如果不标记 1 为已访问，你会从 2 走回 1，再从 1 走回 2……永远出不来。visited 就是”已经走过的地方不再走”，保证每个节点只处理一次，时间 $O(N+M)$ 。

教材 9.2 B62 Print a Path 进一步展示了 DFS 的路径追踪能力：用栈记录当前的路径，到达目标节点时栈中就是完整路径。回溯时弹出栈顶——“进栈是前进，出栈是后退”。

DFS 的回溯天然地产生了一棵 DFS 树。原图的边被分成两类：树边（DFS 经过的边）和非树边。非树边又分为前向边、后向边和横叉边——这些分类在判断环、找割点和桥时非常有用（后面 04-06 SCC 就用到了后向边的性质）。

BFS：为什么”层层扩展”能找最短路？

BFS 用一个队列来实现。起点入队，然后不断取出队头，把它的所有未访问邻居入队。

为什么 BFS 找到的一定是最短路径（在无权图中）？ 关键在于队列的”先进先出”性质。起点先入队（距离 0），它的直接邻居第二批入队（距离 1），邻居的邻居第三批入队（距离 2）……同一批入队的节点距离起点一样远。因此，当节点 $v$ 第一次被访问时，经过的路径长度就是最短距离——任何更短的路径必然经过更早入队的节点，而那些节点早就处理过了。

教材 9.3 B63 幅優先探索（BFS）用迷宫问题展示了这个原理：把迷宫的每个空格看成顶点，相邻空格之间有边，BFS 就能找到从起点到终点的最少步数。

如果用栈代替队列呢？ 你就得到了 DFS！栈是后进先出，最后入队的邻居最先被处理，所以你总是先往深里走。

DFS vs BFS：什么时候用哪个？

	DFS	BFS
数据结构	栈（递归调用栈）	队列
搜索顺序	先往深处走	先往宽处走
天然求什么	连通性、环检测、路径还原	无权图最短路、按层遍历
空间	$O(N)$ （递归深度）	$O(N)$ （队列大小）
典型用途	SCC、拓扑排序、树上问题	最短路、二分图判定

竞赛中的经验：需要最短距离就用 BFS，其他大部分情况 DFS 更灵活。

理论 + 代码

邻接表

#include <vector>
using namespace std;

const int MAXN = 100006;
vector<int> adj[MAXN]; // ① adj[u] 存 u 的所有邻居

// 读入
int N, M;
scanf("%d%d", &N, &M);
for (int i = 0; i < M; i++) {
    int a, b;
    scanf("%d%d", &a, &b);
    adj[a].push_back(b); // ② 无向图：两边都加
    adj[b].push_back(a);
}

逐行解析：

① vector<int> adj[MAXN]：每个顶点一个 vector，存它的邻居列表。这比邻接矩阵省空间（ $O(N+M)$ vs $O(N^2)$ ），遍历邻居时也更快（只看实际存在的边）。
② 无向图的边需要双向添加。有向图只加一个方向。

DFS

bool visited[MAXN];

void dfs(int u) {
    visited[u] = true;          // ① 标记已访问
    for (int v : adj[u]) {     // ② 遍历 u 的所有邻居
        if (!visited[v])       // ③ 只访问未访问的
            dfs(v);            // ④ 递归深入
    }
}

// 调用
dfs(1); // 从顶点 1 出发

逐行解析：

① visited 数组防止重复访问。没有它会死循环——想想三角形 1→2→3→1，不标记就会无限绕圈。
②③④ 对每个未访问的邻居递归调用。递归天然实现了”回溯”——函数返回就是回到岔路口。

时间复杂度 $O(N + M)$ ：每个顶点访问一次，每条边检查两次。

DFS 和递归的关系：递归调用栈就是 DFS 的栈。每次 dfs(v) 就是”走到 $v$ “，函数返回就是”回到上一个岔路口”。如果你不想用递归（怕栈溢出，比如 $N = 10^6$ ），可以用显式栈模拟——效果完全一样。

BFS

#include <queue>

int dist[MAXN]; // 距离（-1 表示未访问）

void bfs(int start) {
    memset(dist, -1, sizeof(dist));
    queue<int> q;
    dist[start] = 0;    // ① 起点距离为 0
    q.push(start);
    while (!q.empty()) {
        int u = q.front(); q.pop(); // ② 取队头
        for (int v : adj[u]) {      // ③ 遍历邻居
            if (dist[v] == -1) {    // ④ 未访问
                dist[v] = dist[u] + 1; // ⑤ 距离+1
                q.push(v);              // ⑥ 入队
            }
        }
    }
}

逐行解析：

① 起点距离为 0。dist 数组同时承担了 visited 的功能： $-1$ 表示未访问， $\ge 0$ 表示已访问且记录了距离。
② 先进先出：保证按距离从近到远处理。这是 BFS 找最短路的关键——如果用栈（后进先出），就变成 DFS 了。
⑤ 因为是第一次到达，dist[u] + 1 就是最短距离。为什么？因为队列保证了所有距离 $\le dist[u]$ 的节点都已经处理过了，不存在更短的路径。
总时间 $O(N + M)$ 。

模拟走一遍

图：1-2, 1-3, 2-4, 2-5, 3-6

DFS 从 1 出发（邻居按从小到大）：

dfs(1) → 进入 2 → 进入 4 → 回到 2 → 进入 5 → 回到 2 → 回到 1 → 进入 3 → 进入 6
访问顺序：1, 2, 4, 5, 3, 6

递归栈的变化：[1] → [1,2] → [1,2,4] → [1,2] → [1,2,5] → [1,2] → [1] → [1,3] → [1,3,6]

BFS 从 1 出发：

步骤	队列	取出	dist 变化
初始	[1]	—	dist[1]=0
1	[2,3]	1	dist[2]=1, dist[3]=1
2	[3,4,5]	2	dist[4]=2, dist[5]=2
3	[4,5,6]	3	dist[6]=2
4-6	空	4,5,6	无新邻居

dist = [0, 1, 1, 2, 2, 2]。从 1 到 6 的最短距离是 2（路径 1→3→6）。

例题

例题 1：TB A61 — Adjacent Vertices

题目：给定 $N$ 个顶点 $M$ 条边的无向图。对每个顶点 $k$ （ $1 \le k \le N$ ），输出与 $k$ 相邻的所有顶点编号。

数据范围： $2 \le N, M \le 10^5$

—— AtCoder Tessoku Book A61

分析：图的输入练习。读入边，建邻接表，按格式输出。

代码：

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int N, M;
    scanf("%d%d", &N, &M);
    vector<vector<int>> adj(N + 1);
    for (int i = 0; i < M; i++) {
        int a, b;
        scanf("%d%d", &a, &b);
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    for (int k = 1; k <= N; k++) {
        sort(adj[k].begin(), adj[k].end()); // ① 排序使输出有序（题目不要求但更美观）
        printf("%d: {", k);
        for (int j = 0; j < (int)adj[k].size(); j++) {
            if (j) printf(", ");
            printf("%d", adj[k][j]);
        }
        printf("}\n");
    }
    return 0;
}

逐行解析：

① sort 不是必须的（题目说顺序无所谓），但排序后输出更整洁。
邻接表是图论的基础中的基础——后面所有图论题都从这里开始。

例题 2：TB A62 / M&A 043 — Depth First Search

题目： $N$ 个顶点 $M$ 条边的无向图。从顶点 1 出发做 DFS，按访问顺序输出所有能到达的顶点编号。

数据范围： $1 \le N, M \le 10^5$

—— AtCoder Tessoku Book A62

分析：裸的 DFS 遍历。从 1 出发，递归访问所有可达顶点。

代码：

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

const int MAXN = 100006;
vector<int> adj[MAXN];
bool visited[MAXN];
vector<int> order;

void dfs(int u) {
    visited[u] = true;
    order.push_back(u);              // ① 记录访问顺序
    sort(adj[u].begin(), adj[u].end()); // ② 按编号从小到大访问
    for (int v : adj[u]) {
        if (!visited[v]) dfs(v);
    }
}

int main() {
    int N, M;
    scanf("%d%d", &N, &M);
    for (int i = 0; i < M; i++) {
        int a, b;
        scanf("%d%d", &a, &b);
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    dfs(1);
    for (int i = 0; i < (int)order.size(); i++) {
        if (i) printf(" ");
        printf("%d", order[i]);
    }
    printf("\n");
    return 0;
}

逐行解析：

① 在进入节点时立即记录，保证按 DFS 访问顺序输出。
② 排序邻居保证按编号从小到大访问（题目通常这样要求）。

例题 3：M&A 046 / TB B63 — 幅優先探索（BFS）

题目： $R \times C$ 的网格迷宫。起点 $(S_r, S_c)$ ，终点 $(T_r, T_c)$ 。. 可通行，# 是墙。求从起点到终点的最短步数。

数据范围： $1 \le R, C \le 1000$

—— AtCoder M&A 046

分析：网格上的最短路 = 无权图 BFS。把每个格子看成节点，上下左右有边。

代码：

#include <cstdio>
#include <queue>
#include <cstring>
using namespace std;

const int MAXN = 1006;
char grid[MAXN][MAXN];
int dist[MAXN][MAXN];
int R, C;
int dr[] = {-1, 1, 0, 0}, dc[] = {0, 0, -1, 1};

int main() {
    scanf("%d%d", &R, &C);
    int sr, sc, tr, tc;
    scanf("%d%d%d%d", &sr, &sc, &tr, &tc);
    for (int i = 1; i <= R; i++) scanf("%s", grid[i] + 1);

    memset(dist, -1, sizeof(dist));
    queue<pair<int,int>> q;
    dist[sr][sc] = 0;                 // ① 起点距离 0
    q.push({sr, sc});
    while (!q.empty()) {
        auto [r, c] = q.front(); q.pop();
        for (int d = 0; d < 4; d++) { // ② 四方向
            int nr = r + dr[d], nc = c + dc[d];
            if (nr < 1 || nr > R || nc < 1 || nc > C) continue; // ③ 越界
            if (grid[nr][nc] == '#') continue;                   // ④ 墙壁
            if (dist[nr][nc] != -1) continue;                    // ⑤ 已访问
            dist[nr][nc] = dist[r][c] + 1;
            q.push({nr, nc});
        }
    }
    printf("%d\n", dist[tr][tc]);
    return 0;
}

逐行解析：

① BFS 从起点开始，距离初始化为 0。
② 上下左右四个方向。
③④⑤ 三个剪枝条件：越界、墙壁、已访问。
因为是无权图，BFS 第一次到达终点的距离就是最短路径。

例题 4：TB A70 — Lanterns

题目： $N$ 个灯（ $N \le 10$ ），初始有开有关。 $M$ 种操作，第 $i$ 种同时翻转灯 $X_i, Y_i, Z_i$ 。最少操作几次让所有灯都亮？

数据范围： $3 \le N \le 10$ ， $0 \le M \le 100$

—— AtCoder Tessoku Book A70

分析： $N$ 个灯只有 $2^N \le 1024$ 种状态。把状态当作图的节点，每次操作是一条边。BFS 求从初始状态到全亮状态的最少步数。

代码：

#include <cstdio>
#include <queue>
#include <cstring>
using namespace std;

int dist[1 << 10]; // 状态空间：2^10 = 1024
int flips[110];    // 每种操作翻转的掩码
int N, M;

int main() {
    scanf("%d%d", &N, &M);
    int start = 0;
    for (int i = 0; i < N; i++) {
        int a; scanf("%d", &a);
        if (a) start |= (1 << i);    // ① 初始状态编码为二进制
    }
    for (int i = 0; i < M; i++) {
        int x, y, z;
        scanf("%d%d%d", &x, &y, &z);
        flips[i] = (1 << (x-1)) | (1 << (y-1)) | (1 << (z-1)); // ② 操作掩码
    }

    memset(dist, -1, sizeof(dist));
    queue<int> q;
    dist[start] = 0;
    q.push(start);
    int goal = (1 << N) - 1;              // ③ 全亮状态：所有位为 1
    while (!q.empty()) {
        int s = q.front(); q.pop();
        if (s == goal) {                   // ④ 到达目标
            printf("%d\n", dist[s]);
            return 0;
        }
        for (int i = 0; i < M; i++) {
            int ns = s ^ flips[i];         // ⑤ 翻转操作 = 异或
            if (dist[ns] == -1) {
                dist[ns] = dist[s] + 1;
                q.push(ns);
            }
        }
    }
    printf("-1\n");
    return 0;
}

逐行解析：

① 用二进制位表示灯的状态：第 $i$ 位 = 1 表示灯 $i$ 亮。
② 每种操作翻转 3 个灯 = XOR 这 3 位。
③ 目标状态是所有位都是 1，即 $(1 << N) - 1$ 。
⑤ s ^ flips[i] 就是”对状态 $s$ 执行操作 $i$ “——异或实现翻转。
这是 BFS 的经典变体：状态空间搜索。图的节点不是物理位置，而是抽象状态。

例题 5：TB A65 — Road to Promotion

题目：公司 $N$ 个员工，1 号是社长。每个员工 $i$ （ $i \ge 2$ ）的直属上司是 $A_i$ （ $A_i < i$ ）。求每个员工有多少个下属（直接+间接）。

数据范围： $2 \le N \le 10^5$

—— AtCoder Tessoku Book A65

分析：这是一棵树（每个员工只有一个直属上司）。用 DFS 统计子树大小：员工的下属数 = 子树大小 - 1。

代码：

#include <cstdio>
#include <vector>
using namespace std;

const int MAXN = 100006;
vector<int> children[MAXN]; // 只存子节点（有向树）
int sub[MAXN];              // 子树大小

void dfs(int u) {
    sub[u] = 1;                     // ① 自己算一个
    for (int v : children[u]) {
        dfs(v);
        sub[u] += sub[v];           // ② 累加子节点的子树大小
    }
}

int main() {
    int N;
    scanf("%d", &N);
    for (int i = 2; i <= N; i++) {
        int a;
        scanf("%d", &a);
        children[a].push_back(i);   // ③ 建有向树
    }
    dfs(1);
    for (int i = 1; i <= N; i++) {
        printf("%d%c", sub[i] - 1, " \n"[i == N]); // ④ 下属数 = 子树大小-1
    }
    return 0;
}

逐行解析：

① 初始子树大小为 1（自己）。
② 递归处理子节点后，把子节点的子树大小累加到当前节点。
③ 因为 $A_i < i$ ，这是一棵有向树，只需存子节点。
④ 下属数 = sub[i] - 1（不含自己）。

参考文献

理论讲义 — AtCoder Algorithm Lectures

グラフ理論用語集（图论术语定义）

教材讲解 — 競技プログラミングの鉄則第 9 章

基础练习 — アルゴリズムと数学演習問題集

系统练习 — 競技プログラミングの鉄則

系列索引

第零章基础工具

第一章搜索技术

第二章数学基础

第三章数据结构

第四章图论

第五章动态规划

第六章贪心

第七章字符串

第八章进阶

图的遍历

图论的地基——DFS "一条路走到黑"和 BFS "层层扩展"，以及图的基本存储方式

前言

问题的本质

图是什么？怎么存？

DFS：为什么”走到黑”不会漏掉节点？

BFS：为什么”层层扩展”能找最短路？

DFS vs BFS：什么时候用哪个？

理论 + 代码

邻接表

DFS

BFS

模拟走一遍

例题

例题 1：TB A61 — Adjacent Vertices

例题 2：TB A62 / M&A 043 — Depth First Search

例题 3：M&A 046 / TB B63 — 幅優先探索（BFS）

例题 4：TB A70 — Lanterns

例题 5：TB A65 — Road to Promotion

参考文献

系列索引

图的遍历