广度优先搜索_专项题单练习

BFS无权最短路

问题识别方式

给定一个迷宫，找到从起点到终点的最短距离——最短路径，一般来说给定一个迷宫或一张图，给定起点，找到达某些位置的最短路长度或方案数，可使用BFS求最短路的策略。

解决方案

对于此类题目，首先要明确起点位置，从起点出发做BFS，根据题目给定规则（固定方向、u->v）考虑当前点能够走到的点，计算出每个能走到的点的最短距离，同时对于走到的位置要进行标记，防止重复走到(浪费时间)。

隐式图

问题识别方式

对于隐式图问题，通常根据题目的输入格式，无法直接判断出是图论问题，我们要对题面进行分析。题目中的要求以从一个状态转移到另一个状态的最小次数为主，且每次转移的变换形式是相对固定的。

解决方案

对于此类题目，起始状态即为起点，最终状态为终点，根据题目转移规则，进行建图求最短路。

连通块

问题识别方式

对于此类问题，题目一般的是有多少连在一起的块(水坑、空地)。

解决方案

对于此类题目，遍历所有的结点，如果当前结点是块的一部分且之前没有访问过，则做一次BFS，BFS的次数即为连通块的个数。

0-1BFS

问题识别方式

对于此类问题，对于一个位置有两个大类的操作，通常第一类操作不需要代价，第二类操作需要代价。

解决方案

对于此类题目，使用双端队列进行BFS操作，执行不需要代价的操作后，将到达的位置放入队列头，否则放入队列尾。

多源BFS

问题识别方式

关键词或特征	说明
同时有多个起点	如多个火源、多个感染点、多个初始机器人、多个起始任务
目的是求最短距离/最少步骤	常出现：“多久扩散到所有点”“最少时间完成”“离最近目标的距离”
扩散类场景	如火烧森林、疫情扩散、腐烂橘子、水漫金山、传染病
如果用普通 BFS 需要重复多次	单源 BFS 会导致每次独立计算，然后取最小值，此时可并行

解决方案

与普通 BFS 的区别只有一点 —— 初始队列不是一个点，而是多个点同时入队，相当于它们一起作为距离为 0 的起始源头并“同时层序扩散”。

flood-fill
问题识别方式
一般来说，问题需要求解的是被包围部分的个数或染色

解决方案

通过四周每个位置做BFS，将可达点进行标记。除去标记点和不可走的点外，剩下即为被包围部分。

建虚点

问题识别方式

识别特征	表现形式
节点之间出现大量“隐式完全连接”	如某一类点之间可以两两到达，但直接建边会爆炸
一对多 / 多对一的跳转关系	从一个点可以瞬间到多个点，或多个点瞬间汇聚到一个状态
共享属性带来的可跳转性	“同颜色能连、同车站能跳、同层能传送、同单词型能变换”
直接 BFS 会导致阶乘 / 全连接爆炸	例如同 group 内要 O(n²) 建边
题目强调状态转换比位置更重要	状态比点更像关键节点

解决方案

当节点间存在共享属性导致“隐式全连接”或“一对多跳转”时，用虚点表示该共享属性，并把 BFS 建立在“原点 + 虚点”的新图上，从而使复杂跳转简单化。

双向BFS

问题识别方式

题目中设计的中间状态较多，强行枚举会超时

解决方案

如果题目给出初始的状态和结束状态，可以尝试折半查找的方式，分别从起点和终点做BFS各走一半距离。

分层BFS

问题识别方式

识别特征	表现形式
同一节点在不同状态有不同行为	例如是否有钥匙、是否用过特殊能力、方向不同、时间不同
路径受状态影响	例：开门必须有钥匙、破墙次数有限、是否下过雨、是否变身
限制资源/次数的最短路	“最多可以用 K 次”、“最多可以破墙 1 次”、“技能只能触发一次”
方向影响下一步	例：转弯代价、移动方向不能回头
图是隐式分层图	同一坐标其实是不同层的不同点
不能用普通 BFS，Dijkstra又嫌重	需要 BFS，但普通 BFS 不够表达状态

解决方案

一、明确状态。根据题目要求，将 BFS 的节点扩展出状态维度，例如破墙次数、当前方向、钥匙集合、时间白夜、技能是否使用等。每一个“位置 + 状态”组合视为 BFS 图中的唯一节点。

二、定义状态转移。在思考“从一个位置走到下一个位置”时，不仅要写出位置的变化，也要写出状态如何变化。状态变化要与题目逻辑一致，例如破一次墙则资源减一，捡到钥匙则状态增加标记，方向不同则转弯代价不同等。

BFS与状态压缩

问题识别方式

识别信号	典型描述	你应该想到什么
需要记录一组“可收集/开关”类状态	钥匙、机关、任务完成情况等	状态不是单一变量
状态具有二元属性	某物“有/无”，“开/关”	可以用 bit 表示
状态组合呈 2^k 的形式	例如最多 k 把钥匙	状态空间是子集
同一位置因状态不同行为不同	到同一坐标，但能不能过门取决于钥匙	访问需要看 mask
坐标 + 状态才唯一决定“访问过没”	visited[x][y] 不够用	必须 visited[x][y][mask]
目标与状态相关	例如“收集所有钥匙再出门”	终点条件取决于 mask
依旧求最短路径（无权）	BFS 特征明显	考虑状态压缩 BFS

解决方案

步骤	要做什么	说明
1. 明确状态的 bit 设计	k 个元素 → k bit，mask 表示子集	mask 的第 i 位表示元素 i 是否拥有
2. BFS 节点升级	节点变为 `(位置, mask)`	“位置 + 状态”共同构成图节点
3. 访问记录升级	`visited[x][y][mask]`	避免错误剪枝
4. 状态转移	走路改变位置，拾取/触发改变 mask	mask 变化用位运算
5. BFS 扩展	像普通 BFS 一样层序推进	队列 push `(nx, ny, new_mask)`
6. 结束条件判断	位置满足要求 & mask 满足要求	常见目标：mask == FULL_MASK
7. 输出路径长度	BFS 层数即最短路	因为仍是无权最短路

拓扑排序

问题识别方式

识别信号	典型描述	你的判断
图是有向图（Directed Graph）	任务有先后约束、课程需先修等	符合拓扑排序场景
存在前置依赖关系（A → B）	“先做A才能做B” / “课程A是B的先修”	依赖结构 = DAG特征
目标是排序或判断是否能完成所有任务	结果需要一个顺序，而不是距离或路径	典型拓扑排序输出
若有环则无解	“环=依赖冲突=无法完成任务”	必须检测环
图不一定连通	多条独立依赖链	BFS可分组件入队
问题与最短路、最少步数无直接关系	输出序列，而非最短路径	BFS角色在于层次处理而不是距离

解决方案

步骤	要做什么	核心说明
1. 统计入度 indegree[]	对每条边 u → v，让 indegree[v]++	入度 = 有多少前置必须完成
2. 建邻接表 graph	记录每个节点能影响谁	有向图存储
3. 将所有入度为 0 的点入队	这些无需依赖，最先执行	拓扑起点（可能多个）
4. BFS（Kahn算法）	每次弹出一个入度为 0 的点加入结果序列	本质是按层剥洋葱
5. 遍历其邻接点并让入度减 1	如果入度减到 0，则入队	模拟前置被满足
6. 最终检查节点数	若输出节点数 < 总节点数 → 有环	用 BFS 检环

【前置知识点】
1、基础数据结构

【后置衔接知识点】
1、最短路

【思维导图】

【题目知识点分类】

竞赛

考级认证

学习入口

广度优先搜索