【BFS｜宽度优先搜索】题型技巧分类总结

个人刷题多次之后发现，这几个类型是综合类题目考查的重点， 基本上如果不是考原题，多半会涉及到： backtracking/DFS， BFS
所以刷BFS是性价比很高的。我结合个人理解总结了一些BFS题目类型和规律，如有不全请多包涵：
（PS 本人极度缺米，如果觉得我写的还不算是垃圾的话请求一点米，不胜感激）

== 综合应用 ==
1.扩散类，从每一个关键点扩散到周围
Queue：首先有很多起始点，比如岸边的点，或者指定的点，烂掉的橘子的点，这些要首先加入queue
Visited： 其次，对于visited，有两种情况：
1）一种是每visit一个点，就update matrix inplace，比如number of Island，烂橘子，fill；
2）另一种是用visited set/array来记录visited；因为扩散类问题不能re-visit去过的点。
题目：
200. Number of Islands


305. Number of Islands II
694. Number of Distinct Islands
417. Pacific Atlantic Water Flow
733. Flood Fill
994. Rotting Oranges



2.检测能否到达，一般是给matrix或者graph，从起始点到指定的终点
Queue：加入起始点， 普通BFS，poll出来的每一个值检查是否是终点
Visited：一定要visited， 用来保证不在circle里循环，有的时候会变成是否全联通， 或者是是否能达到所有的点，这个时候就是检查visited set的大小了
题目：
490. The Maze


399. Evaluate Division
1306. Jump Game III
261. Graph Valid Tree


841. Keys and Rooms



3.从一个点到另一个点能到达的最短路径， 每个点到下一个点的代价相同的情况
最短路径，当每个点的代价相同，就是level order BFS， 如果想要优化速度，就是使用Bi-directional
BFS，双向level的BFS好处就是，假设每次搜索的分支因子是r，搜索L层，一般BFS总的搜索状态数是r^L；
双向BFS算法，每个方向只需要搜索L/2层，因此，搜索状态数是2*(r^(L/2))
Queue：保存起始点
Visited：保存走过的点
step：保存层数
题目：
773. Sliding Puzzle
1197. Minimum Knight Moves
1293. Shortest Path in a Grid with Obstacles Elimination：这题的难点无非就是visited多了一种状态， 每一个点多了一个状态：使用elimination的次数，即int[] start = {0, 0, 0
864. Shortest Path to Get All Keys：这题的难点类似上一题，也就是每一个节点多了一种状态：当前这个点的key收集情况，visited也多了一个维度，使得同一个点可以重复visit很多次，只要钥匙的状态不同，start = {0, 0, 0}
LintCode 1364. the minium distance：这题的难点就是多了一个传送门，相当于除了expand4个方向，还多一个传送门方向，用过的所有传送门就把这个传送门的entry去掉，因为都visited了
LintCode 611. Knight Shortest Path


127. Word Ladder


126. Word Ladder II

4.从一种点到另一种点的最短路径的和
首先就是有两种点，每种都是有若干个点， 假设A和B
求每一个A到离他最近的B的和，
或者在一堆可能的A里找一个A，他到所有的B的距离最短
int[][] distance: 这种情况首先就是因为有多个点需要计算总distance，所以肯定需要一个distance map，当然也有题目是直接inplace修改
Queue: BFS首先加入的是所有B的点，也就是所有要到达的终点的点，而不是起始点，这样做的好处是：
假如我们从每一个起始点出发，用BFS找寻一个距离最小的终点 O(MN), 对于一个matrix， 最多可能有M*N个这样的起始点，而且对于每一个起始点都要重算，因为无法reuse， 最终O(M*N*M*N) = O(M^2N^2)， 但是如果从每一个终点出发，BFS到每一个起始点，由于distance数组的存在，可以剪枝，这样就能reuse之前算过的值，相当于每个cell只走了一次，最终是O(M*N)
这种有distance表的情况不需要visited matrix
corner case就是要考虑有的点不可达的情况，有的初始matrix就把所有的起始点标成INT MAX了，有的就没有，比如01 Matrix，需要自己手动标记，或者像post office那种，就要再来一个数组记录这个empty的点能到达多少个房子，只有能到达全部房子的才能纳入答案比较。
题目：
542. 01 Matrix
286. Walls and Gates
LintCode 573. Build Post Office II / 317. Shortest Distance from All Buildings


5.从起始点到终点的所有路径中，最大/最小的一条, 节点之间代价不同
题目的问法要么就是minimum effort，要么就是maximum minimum，总是有一个极值在里面， 然后就是，到达周围四个点的代价是不相同的，这个时候就要有取舍
Dijkstra：专做代价不同的图的最短路径
Int[][] distance: 因为到达每一个点都有不同的路径，所以可以visit多次，靠distance更新或剪枝， 初始值根据要求，定义为INT MAX
start={0, 0, 0}： 对于每一个节点，除了坐标以外，还有一个当前的状态
PriorityQueue：这里一定要用heap，每次从局部极值往下发展


题目：
505. The Maze II： 因为有小球滚动的因素在，导致一个点到周围的点的距离（代价）是不相同的
1631. Path With Minimum Effort
1102. Path With Maximum Minimum Value
778. Swim in Rising Water
787. Cheapest Flights Within K Stops

== 补充其他一些基础： 这类记忆模板即可 ==
1.Binary Tree Traverse：
297. Serialize and Deserialize Binary Tree

2.Level Traverse
102. Binary Tree Level Order Traversal
103. Binary Tree Zigzag Level Order Traversal
107. Binary Tree Level Order Traversal II
513. Find Bottom Left Tree Value
LintCode 242. Convert Binary Tree to Linked Lists by Depth

3.Topological Sort：
LintCode 127. Topological Sorting
207. Course Schedule
210. Course Schedule II
269. Alien Dictionary


444. Sequence Reconstruction

4.Graph：
133. Clone Graph

楼主的总结很用心啊！希望也出个DFS/backtracking 总结😊

肤浅如我只知道bfs 要用deque

期待出个出个DFS/backtracking 总结！ mark下

谢谢分享 很要的bfs总结

很好的总结，有个问题，如果面试中follow-up问到如何打印最短路径/步数该怎么办

jxlxt 发表于 2022-07-06 23:33:57
很好的总结，有个问题，如果面试中follow-up问到如何打印最短路径/步数该怎么办

用python的话，直接把path也传到queue里面，每次更新path就行了吧

jxlxt 发表于 2022-07-06 23:33:57
很好的总结，有个问题，如果面试中follow-up问到如何打印最短路径/步数该怎么办

感觉类似word ladder ii，首先在一开始初始化一个map，在bfs的过程中，从一个状态到另一个状态的连线存到map；最后dfs这个map打印路径

同求一个dfs+backtracking 或者dfs+memo类型的

谢谢分享！mark

谢谢分享^^ 紫薯紫薯