广度优先搜索
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、最短路
【思维导图】
【题目知识点分类】
