本文是 leetcode 题目汇总的第 24篇文章，往期内容如下

• 【leetcode题目汇总】1. 区间类问题
• 【leetcode题目汇总】2. 前缀和
• 【leetcode题目汇总】3. 双指针与滑动窗口
  
• 【leetcode题目汇总】4. topK问题
• 【leetcode题目汇总】5. Trie
• 【leetcode题目汇总】6. 设计-基础数据结构
• 【leetcode题目汇总】7. 设计-功能系统
• 【leetcode题目汇总】8. 分拆类问题
• 【leetcode题目汇总】9. 峰谷类问题
• 【leetcode题目汇总】10. 括号类问题
• 【leetcode题目汇总】11. 语法分析类问题
• 【leetcode题目汇总】12. 数据压缩问题
• 【leetcode题目汇总】13. 链表
• 【leetcode题目汇总】14. 分桶
• 【leetcode题目汇总】15. 二分
• 【leetcode题目汇总】16. 计算几何
• 【leetcode题目汇总】17. 树的遍历
• 【leetcode题目汇总】18. 并查集
• 【leetcode题目汇总】19. 排序
• 【leetcode题目汇总】20. 数学
• 【leetcode题目汇总】21. 分治与减治
• 【leetcode题目汇总】22. 模拟

• 【leetcode题目汇总】23. 贪心

这个系列的连载以我在 leetcode 刷过的题为基础，将所有题按比较细的粒度分类汇总，写过的题目的代码在以下 github 仓库中

1

https://github.com/FennelDumplings/leetcode-maxed_out

本文总结了力扣上 2000 题以内的关于BFS的51道题。BFS是一种图结构上的搜索算法，因此它解决的问题基本上也都是图上的搜索问题，包括树的层序遍历、无权图的最短路径、带权图的最短路径、无向图的环、有向图的环、无向图的连通分量、二分图判定、拓扑排序，等等。

BFS有两个题目比较多的场景，一个是Flood Fill，一个是迷宫。从使用的队列来看，可以分为普通队列，优先级队列，双端队列，随机队列等。BFS 还经常与其它算法配合使用，包括复杂状态的表示、状态压缩、多源BFS、双向BFS、有限BFS、常数优化、两次搜索、染色、Astar、模拟退火，等等。

本文的题目主要按照场景、队列类型以及配合使用的算法来聚合，BFS可以解决的树搜索和图搜索问题，会给出一个我个人网站上的链接，上面有对相应的图搜索的算法、题目、题解。

刷完这份题目列表，力扣上的BFS的问题可以说刷爆了。

$1 BFS 可解决的问题

1.1 组合搜索和隐式图搜索

https://chengzhaoxi.xyz/2364.html

1.2 树搜索

https://chengzhaoxi.xyz/10963.html

1.3 图搜索

最短路径

• 无权图最短路径：BFS基本模型，参考后面普通队列的部分

• 带权图最短路径

https://chengzhaoxi.xyz/47644.html

连通分量

https://chengzhaoxi.xyz/21790.html

环

• 无向图的环

https://chengzhaoxi.xyz/b085148b.html

• 有向图的环

https://chengzhaoxi.xyz/f91ac9ea.html

二分图判定

https://chengzhaoxi.xyz/9f3bb921.html

拓扑排序

https://chengzhaoxi.xyz/22315.html

$2队列类型以及配合使用的方法

2.1 无权图最短路径(BFS 基本模型)

• 1311. 获取你好友已观看的视频

• 909. 蛇梯棋

2.2 复杂状态表示和状态转移

定义状态结构体，以及用合适的数据结构维护状态

• 365. 水壶问题

• 317. 离建筑物最近的距离

• 1197. 进击的骑士

• 1210. 穿过迷宫的最少移动次数

• 1293. 网格中的最短路径

2.3 状态压缩

• 864. 获取所有钥匙的最短路径

• 1284. 转化为全零矩阵的最少反转次数

2.4 双端队列(01边权模型)

• 1368. 使网格图至少有一条有效路径的最小代价

• 1263. 推箱子

2.5 优先级队列(带权最短路模型)

• 778. 水位上升的泳池中游泳

• 1102. 得分最高的路径

• 407. 接雨水 II

• 1631. 最小体力消耗路径

• 1514. 概率最大的路径

2.6 随机队列

• 398.随机数索引

• 382.链表随机节点

• 528.按权重随机选择

2.7 多源BFS

• 1162. 地图分析

• 286. 墙与门

• 542. 01 矩阵

• 417. 太平洋大西洋水流问题

2.8 双向BFS

• 127 单词接龙

• 752. 打开转盘锁

• 面试题 17.22. 单词转换

• 433. 最小基因变化

2.9 有限BFS

• 1036. 逃离大迷宫

2.10 常数优化

• 675. 为高尔夫比赛砍树

2.11 两次搜索

• 126. 单词接龙 II

• 934. 最短的桥

2.12 染色

• 913. 猫和老鼠

2.13Astar

• 1091. 二进制矩阵中的最短路径

• 675. 为高尔夫比赛砍树

• 854. 相似度为 K 的字符串

• 773. 滑动谜题

2.14 随机化

• 1515. 服务中心的最佳位置

$3 经典场景

3.1 Flood Fill

• 994. 腐烂的橘子

• 面试题 08.10. 颜色填充

• 994. 腐烂的橘子

• 面试题 08.10. 颜色填充

• 200. 岛屿数量

• 130. 被围绕的区域

• 1020. 飞地的数量

• 733. 图像渲染

• 827. 最大人工岛

• 529. 扫雷游戏

3.2 迷宫

• 490. 迷宫

• 505. 迷宫 II

• 499. 迷宫 III

• 1391. 检查网格中是否存在有效路径

• 1210. 穿过迷宫的最少移动次数

• LCP 13. 寻宝

●【面试好题】子数组和排序后的区间和

●【概率面试题连载】24. 选票盒

●【动态规划的优化】2.哈希表优化DP