Appearance
广度优先搜索（BFS）
2026 大纲 五（三）图的遍历 2. 广度优先搜索（第 1 小项见《DFS》，DFS 与 BFS 的完整对照表也在那一篇）。
一圈一圈往外推
DFS 是"一条路走到黑"，BFS 正好相反：先访问起点，再访问它的全部邻接点，然后访问这些邻接点的全部未访问邻接点。像往水里丢一颗石子，波纹一圈一圈往外扩。
要做到这一点，得记住"已经访问过、但邻居还没展开"的那些顶点，并且按记录的先后顺序去展开。"先记的先取"正是队列（FIFO）的语义，所以 BFS 用队列。
这里有个值得停一下的观察：
🔴 把队列换成栈，同一份代码就变成了 DFS。 遍历策略并不写在算法骨架里，它藏在辅助容器"取出元素的顺序"里。
先动手看一眼
盯住队列那一栏：每出队一个顶点，它的未访问邻居就整批涌进队尾。同一层的顶点总是挨在一起进队——这个现象就是后面"层次划分唯一"的全部内容。
入队即置位，这一条不能挪
c
// ── 邻接表版
void BFS_AdjList(int v) {
int queue[MAX_VERTEX], front = 0, rear = 0;
printf("%d ", v); visited[v] = 1; queue[rear++] = v;
while (front != rear) {
int u = queue[front++];
ArcNode *p = AdjList[u].first;
while (p != NULL) {
int w = p->adjvex;
if (!visited[w]) {
printf("%d ", w);
visited[w] = 1; // 置位与入队同时发生
queue[rear++] = w;
}
p = p->next; // 🔴 推进必须在 if 之外，否则死循环
}
}
}
// ── 遍历整个图（处理非连通图）；启动次数 = 无向图连通分量个数
void BFSTraverse(void) {
for (int i = 0; i < n; i++) visited[i] = 0;
for (int i = 0; i < n; i++)
if (!visited[i]) BFS(i);
}visited[w] = 1 必须与入队同时发生，挪到出队时才置位是错的。看个反例：图
这条纪律还顺带保证了另一件事：每个顶点最多入队一次，rear 最大只到
外层的 for 循环同样不能省：一次 BFS 只走遍一个连通分量。启动次数 = 无向图连通分量个数（有向图上与强连通分量个数没有对应关系，与 DFS 同理）。
复杂度与 DFS 完全相同：邻接表
空间也是
层次划分唯一，序列不唯一
这是 BFS 最要紧的一条性质，也是它能求最短路径的全部根据。
层号
序列则会变：起点不同、每个顶点的邻接点检查次序不同，序列就不同。但同层内部怎么排，都不影响任何一个顶点的层号。
🔴 层次划分唯一 + 序列不唯一 = BFS 求最短路径是可靠的，而具体的遍历序列不是唯一答案。判"下列哪个不是 BFS 序列"的题就建立在后半句上。
由此还得到 BFS 树的一条 DFS 树没有的性质：
🔴 跨层不超过 1：无向图中对任意边
，有 。
理由：设
BFS 生成树由所有"引起顶点首次被访问"的边构成。树上从根到任一顶点的路径，就是原图中边数最少的路径——因为
判一个序列是不是合法的 BFS 序
给一张图和四个序列，问哪个不是 BFS 序列。判法是逐个卡两条：
- 序列的第一个顶点是起点，它自己一层。
- 从第 2 个开始，每个顶点必须是"当前已出队顶点"的未访问邻居。换句话说，把序列切成层：第 1 层是起点的全部邻居，第 2 层是这些邻居的全部未访问邻居……每一层必须整块出现，不能有某层的顶点插到下一层中间去。
最快的手法是先按起点算出每个顶点的层号，再看序列的层号是不是单调不减。层号跳回去了，或者某一层还没排完就出现了下一层的顶点，那就不合法。
⚠️ 同层内部的次序是自由的，别拿"编号从小到大"去否定选项——那样会把好几个合法序列判成非法。
BFS 的"最短"是边数最少，不是权和最小
这句话要拆成两个方向记，因为真题两个方向都考过。
方向一：带权图上 BFS 不能求最短路。 BFS 把每条边都当作等长的一步，只保证边数最少。反例：
方向二：各边权都相等的图上，BFS 恰好就是最短路算法。 权全为 1 时"边数最少"与"权和最小"是同一件事，BFS 直接给出答案。
第二个方向有一处特别值得留意——它常常和最小生成树摆在一起考：
🔴 Prim 和 Kruskal 求出的最小生成树，不是最短路径树。 即使各边权都为 1、MST 的总权值确实最小，树上从某个顶点到其余顶点的路径也未必最短。
举个最小的例子：四个顶点连成一个环
与树的层序遍历的关系
二叉树的层序遍历就是 BFS 在树上的特例，代码几乎一样，差别只有一处：树里不需要 visited[]。因为树中从根到任一结点的路径唯一，一个结点不可能从两条路径被到达；图里有环，所以必须有它。
七顶点无向图的 BFS 走查与层次划分，以及与 DFS 序列的对照（想手动模拟就展开）
与 DFS 那篇用的是同一张无向图，便于对照：
| 顶点 | 边链表 |
|---|---|
| 0 | 1 → 2 |
| 1 | 0 → 3 → 4 |
| 2 | 0 → 5 → 6 |
| 3 | 1 |
| 4 | 1 → 5 |
| 5 | 2 → 4 |
| 6 | 2 |
从顶点 0 出发：
| 步 | 出队顶点 | 检查其邻居 | 新入队 | 队列状态（出队后） | 已输出 |
|---|---|---|---|---|---|
| 0 | — | — | 0 | 0 | |
| 1 | 0 | 1, 2 | 1, 2 | 0 1 2 | |
| 2 | 1 | 0(已), 3, 4 | 3, 4 | 0 1 2 3 4 | |
| 3 | 2 | 0(已), 5, 6 | 5, 6 | 0 1 2 3 4 5 6 | |
| 4 | 3 | 1(已) | — | 0 1 2 3 4 5 6 | |
| 5 | 4 | 1(已), 5(已) | — | 0 1 2 3 4 5 6 | |
| 6 | 5 | 2(已), 4(已) | — | 0 1 2 3 4 5 6 | |
| 7 | 6 | 2(已) | — | 0 1 2 3 4 5 6 |
BFS 序列：0 1 2 3 4 5 6，层次划分为
与 DFS 的对照：同一张图、同一个起点、同一份邻接表，DFS 序列是 0 1 3 4 5 2 6。DFS 在第 2 步就一头扎到 3 号顶点（离起点 2 条边），BFS 则把离起点 1 条边的顶点全部处理完才往下走。
序列的不唯一性：若把顶点 0 的链改成 2 → 1、顶点 1 的链改成 4 → 3 → 0、顶点 2 的链改成 6 → 5 → 0，得到 0 2 1 6 5 4 3——层次划分不变，只是同层内部的次序变了。
BFS 生成树：树边为
图注：左图顶点旁的数字是访问次序，虚线把顶点按"距起点的层"切开—— 一层处理完才推进到下一层，虚线就是波纹的形状。右图是把"首次到达"用的那些边抽出来构成的 BFS 树。与 DFS 那篇同一张原图的 DFS 树对比：这里
直接连着 三个孩子， 树很矮很宽；DFS 树则是一条长链。同一个图，两种遍历给出形状完全不同的生成树。 图源：殷人昆《数据结构——用面向对象方法与 C++ 描述》（第 2 版）图8.13 广度优先搜索示例，p366
由"跨层不超过 1"直接得到的二部图判定法（要写这段代码时展开）
跑一遍 BFS 求出每个顶点的层号
- 若每条边两端层号奇偶性都不同（差恰为 1），按层号奇偶把顶点分成两组就是一个合法二分，图是二部图；
- 若存在同层边
（ ），则"根→ "（ 条边）+ 边 + " →根"（ 条边）构成一条长度 的奇数长度闭合回路，图中必含奇环，不是二部图（判定定理见图的基本概念）。
落成代码就是"相邻必异色"：
c
int color[MAX_VERTEX]; // -1 未染色；0 / 1 两种颜色
int isBipartite(int n) {
for (int i = 0; i < n; i++) color[i] = -1;
int queue[MAX_VERTEX];
for (int s = 0; s < n; s++) {
if (color[s] != -1) continue; // 该分量已处理过
int front = 0, rear = 0;
color[s] = 0;
queue[rear++] = s;
while (front != rear) {
int u = queue[front++];
for (ArcNode *p = AdjList[u].first; p; p = p->next) {
int w = p->adjvex;
if (color[w] == -1) {
color[w] = 1 - color[u]; // 相邻必异色 → 层号奇偶交替
queue[rear++] = w;
} else if (color[w] == color[u])
return 0; // 同色边 → 存在奇环 → 不是二部图
}
}
}
return 1;
}两处要点：
- 外层的
for (s)循环不能省。判定要对每个连通分量各做一次，否则非连通图只判了一部分。 else if里的else不能丢。已染色时才需要检查冲突；刚染上的色必然是异色，重复检查是多余的。
用走查那张图跑：
邻接矩阵版实现，以及用 BFS 数连通分量
c
// ── 邻接矩阵版：每次出队都要扫一整行才能找齐 u 的邻接点
void BFS(int v) {
int queue[MAX_VERTEX], front = 0, rear = 0;
printf("%d ", v);
visited[v] = 1;
queue[rear++] = v; // 入队与置位同时完成
while (front != rear) {
int u = queue[front++];
for (int w = 0; w < n; w++)
if (Graph[u][w] == 1 && !visited[w]) {
printf("%d ", w);
visited[w] = 1;
queue[rear++] = w;
}
}
}
int countComponents(void) {
for (int i = 0; i < n; i++) visited[i] = 0;
int cnt = 0;
for (int i = 0; i < n; i++)
if (!visited[i]) { BFS(i); cnt++; } // 每启动一次 BFS 就多一个分量
return cnt;
}走查：7 个顶点，边为 BFS(0) 访问 cnt=1；BFS(3) 访问 cnt=2；BFS(5) 访问 cnt=3。连通分量数 = 3。
同时得到 BFS 生成森林：三棵树的边分别是
⚠️ 这条只对无向图成立。
考点速记
三条结论：
- 队列 → 逐层扩展；把队列换成栈就变成 DFS，算法骨架不变。
visited必须在入队时置位，这同时保证了正确性与"每个顶点最多入队一次"。- 层次划分唯一、序列不唯一；BFS 树上任意一条原图边的两端层号之差不超过 1。
这一节在真题里被考过的形式（下方「真题练习」逐题对应）：
- 判某序列不是 BFS 序列：四个选项里三个合法。手法是先按该起点算出各顶点的层号，再看序列的层号是否单调不减、每层是否整块出现。同层内部次序自由，别按编号大小否定。
- 邻接表上 BFS 的时间复杂度：
，四个选项通常是 / / / 。 - 等权图上谁能求最短路：给一个"各边权均为 1 的无向连通图"，问 Prim / Kruskal / BFS 中哪些一定能求出从某顶点到其余各顶点的最短路径。答案只有 BFS——最小生成树最小化的是全树权值和，不是各顶点到源点的距离。
- 带权图上 BFS 行不行：作为错误命题出现，"可用 BFS 求带权图中每一对顶点的最短路径"是错的。
易错：BFS 的"最短"是边数最少。 边权不全相等时它给出的不是最短路，要用 Dijkstra；边权全相等时它才恰好等价于最短路算法。
易错：最小生成树不是最短路径树。 四顶点等权环去掉一条边得到的链，就是"MST 权和最小、但树上两点距离比原图远"的最小反例。
易错：
visited在入队时置位，不是出队时。 挪到出队，同一个顶点会被重复入队，队列还可能越界。
教材出处
- 严蔚敏《数据结构（C 语言版）》（第 2 版）印刷 p164，§6.5.2： BFS 的三步过程描述，以及"先访问的顶点其邻接点亦先被访问。为此，算法实现时需引进队列 保存已被访问过的顶点"；同页给出 BFS 算法（算法 6.7）， 在
if (!visited[w])分支内同时完成访问、置visited[w]=true与入队。 - 同书印刷 p164：广度优先生成树—— "图 6.17(c) 中所示的所有顶点加上标有实箭头的边，构成一棵以
为根的树， 称为广度优先生成树"。 - 同书印刷 p164（算法分析）： "每个顶点至多进一次队列……广度优先搜索遍历图的时间复杂度和深度优先搜索遍历相同， 即当用邻接矩阵存储时，时间复杂度为
；用邻接表存储时，时间复杂度为 。 两种遍历方法的不同之处仅仅在于对顶点访问的顺序不同。" - 同书印刷 p170（§6.6.2 开头）： 求"中转次数最少"的路线时"只需从顶点 A 出发对图做广度优先搜索…… 由此所得的广度优先生成树上，从根顶点 A 到顶点 B 的路径就是中转次数最少的路径"。
图源：殷人昆《数据结构——用面向对象方法与 C++ 描述》（第 2 版）图8.13，p366。
相关知识
DFS（栈驱动的对称版本，完整对照表在那一篇）｜ BFS 最短路径（