建议用时：24～30 分钟
今日目标：理解邻接矩阵和邻接表，分清 DFS 与 BFS，知道怎样把网格看成图并进行洪水填充，能追踪一段按编号顺序访问的 BFS 程序。大纲定位：图的邻接矩阵与邻接表、DFS、BFS、Flood Fill；今天只学习现行入门级大纲要求的图遍历内容。
纸上可以直接画点和线，程序却需要把关系存进数组。通常先把 n 个顶点编号为 1...n 或 0...n-1，再选择邻接矩阵或邻接表。
无论采用哪一种存储，同一张图的顶点和边都没有改变；改变的只是程序查询、遍历这些边的方式。选择题经常考“空间多少”“判断两点相邻是否方便”“一条无向边要存几次”。
邻接矩阵 g[u][v] 表示从顶点 u 到顶点 v 是否有边。无权图常用 0/1；带权图可以存边权，没有边时用一个特殊值表示。
g[u][v] == g[v][u]，矩阵关于主对角线对称；g[u][v] 表示 u→ v，矩阵通常不对称；g[i][i] 均为 0；矩阵的优点是查询 u,v 是否直接相连很方便，只看一个格子；缺点是无论实际有多少条边，都需要 n2 个位置。顶点很多、边很少时，大量格子都是 0。
邻接表为每个顶点保存一列相邻顶点。假设有无向边 (u,v)，要把 v 加进 u 的表，也要把 u 加进 v 的表，因此一条无向边通常出现两次；有向边 u→ v 只需把 v 放进 u 的出边表。
邻接表保存的项目数与实际边数接近，适合边较少的稀疏图。要枚举 u 的所有邻居也很方便；但要判断特定的 u,v 是否相邻，可能需要在 u 的整张表里寻找。
| 比较 | 邻接矩阵 | 邻接表 |
|---|---|---|
| 主要空间 | n2 | 与 n+m 同量级 |
| 判断指定边是否存在 | 直接查一个格 | 在邻居表中查找 |
| 枚举一个点的邻居 | 扫一整行 | 只扫实际邻居 |
| 更适合 | 顶点不多或边很密 | 顶点多、边较少 |
这里 m 表示边数。初赛一般考理解，不必死记复杂符号；只要明白矩阵“整张表都存”，邻接表“有边才存”。
深度优先搜索 DFS 的过程像走迷宫：从当前顶点选择一个尚未访问的邻居继续深入；没有新邻居时退回上一个顶点。递归函数天然利用系统调用栈，也可以自己用栈实现。
void dfs(int u) {
vis[u] = true;
for (int v : adj[u])
if (!vis[v]) dfs(v);
}
vis 很重要：图中可能有环。没有访问标记，程序可能沿 1→2→3→1 不断绕圈。对于不连通图，只从 1 做一次 DFS 只能访问 1 所在的连通分量；要遍历全图，还需依次检查每个未访问顶点，并从它重新开始。
DFS 的具体序列不是唯一的。若邻接点按编号从小到大处理和从大到小处理，走出的先后顺序可能不同，但同一起点所有可达顶点都会被访问。
BFS 使用队列。起点先入队并标记；之后不断取出队首 u，把 u 所有尚未访问的邻居标记并加入队尾。
q.push(s);
vis[s] = true;
while (!q.empty()) {
int u = q.front(); q.pop();
for (每个与 u 相邻的 v)
if (!vis[v]) {
vis[v] = true;
q.push(v);
}
}
应当在入队时立即标记。若等到出队才标记，同一顶点可能被多个前驱反复放入队列，虽然有些程序最后结果仍对，却会产生重复工作甚至队列溢出。
本日程序的队列变化如下：
| 取出顶点 | 新发现顶点 | 操作后队列 |
|---|---|---|
| 1 | 2，3 | 2，3 |
| 2 | 4 | 3，4 |
| 3 | 无（4 已标记） | 4 |
| 4 | 5 | 5 |
| 5 | 无 | 空 |
所以输出为 1 2 3 4 5。把每轮的“队首、发现谁、队列内容”写出来，是阅读 BFS 程序最可靠的方法。
BFS 先处理距离起点 0 的顶点，再处理距离 1、2、3……的顶点。某顶点第一次被发现时，不可能还存在一条边数更少但尚未处理的路径，因此第一次得到的距离就是最少边数。
可以设置 dist[s]=0，每当从 u 第一次发现 v 时令
dist[v] = dist[u] + 1;
这个结论适用于每条边代价相同或只问经过几条边的情形。如果边权不同，边数最少不一定总权值最小，不能直接把普通 BFS 当成带权最短路算法。
CSP-J 2022 完善程序曾以队列和网格扩展考查 BFS。读这类题时，网格中的每个位置可以看成顶点，上下左右可走关系就是边。
洪水填充（Flood Fill）用于从一个网格位置出发，找出与它连成一片的所有同类位置。可以把每个可走格子看成一个顶点，上、下、左、右相邻关系看成边，然后使用 DFS 或 BFS。
处理每个新位置时要完成三件事：
if (0 <= nx && nx < n && 0 <= ny && ny < m
&& grid[nx][ny] == target && !vis[nx][ny]) {
vis[nx][ny] = true;
q.push({nx, ny});
}
若只需找连通块，DFS 与 BFS 都可以；若还要计算无权网格中的最少步数，通常使用 BFS 并记录距离。
判断某个 DFS 访问顺序是否可能时，不能只看相邻两个字母之间有没有边。DFS 会沿当前分支一直深入，只有当前顶点再也找不到未访问邻居时才回退。最稳的方法是画出递归栈：每到一个顶点就标记访问，按题目允许的邻接次序尝试；若想去的下一个顶点既不是当前点的未访问邻居，也无法在合法回退后到达，该顺序就不可能。
第 1、2 题为 CSP-J 第一轮单选原题；第 3～8 题按现行大纲巩固图的存储、Flood Fill 与 BFS 程序跟踪。
【CSP-J 2021·第 14 题｜原图关系重绘】 无向图的边为 (a,b),(a,c),(b,d),(c,d),(c,e)。以 a 为起点进行深度优先遍历，b,c,d,e 中有可能成为最后一个被访问顶点的共有（ ）个。
A. 1 B. 2 C. 3 D. 4
【CSP-J 2022·第 10 题】 以下关于数据结构的说法不恰当的是（ ）。
A. 图的深度优先遍历常使用栈
B. 栈后进先出，队列先进先出
C. 队列常用于广度优先搜索
D. 栈与队列本质不同，无法用栈实现队列
无向图的邻接矩阵一定具有的性质是（ ）。
A. 所有元素都为 1
B. 关于主对角线对称
C. 每一行元素和都相等
D. 主对角线元素都为 1
在一个由 0 和 1 组成的网格中，从某个值为 1 的格子开始做四方向 Flood Fill，主要目的是（ ）。
A. 把所有格子按数值排序
B. 访问与起点四方向连通的所有 1
C. 用二分查找寻找起点
D. 只访问起点所在的一行
DFS 和 BFS 的具体访问顺序都可能受到邻接点排列顺序的影响。（判断对错）
阅读下面的程序：
#include <iostream>
#include <queue>
using namespace std;
int g[6][6];
bool vis[6];
void addEdge(int u, int v) {
g[u][v] = g[v][u] = 1;
}
int main() {
addEdge(1, 2);
addEdge(1, 3);
addEdge(2, 4);
addEdge(3, 4);
addEdge(4, 5);
queue<int> q;
q.push(1);
vis[1] = true;
while (!q.empty()) {
int u = q.front();
q.pop();
cout << u << ' ';
for (int v = 1; v <= 5; ++v) {
if (g[u][v] && !vis[v]) {
vis[v] = true;
q.push(v);
}
}
}
return 0;
}
程序输出（ ）。
A. 1 2 3 4 5
B. 1 2 4 5 3
C. 1 3 4 5 2
D. 5 4 3 2 1
在程序构造的图中，从顶点 1 到顶点 5 的最少边数是 3。（判断对错）
若删除 addEdge(4, 5);，程序将不会输出顶点 5。（判断对错）
请先独立完成全部题目，并到玄武 OJ 提交今日答案。