【leetcode题目汇总】24. 广度优先搜索 BFS

发布于 2021-11-24 16:11 ，所属分类：2021面试经验技巧分享

本文是 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的问题可以说刷爆了。