BFS
宽度优先搜索。想象一下水波，从中心开始一层一层的往外遍历。一般BFS用来：
- 图中节点的搜索
- 树的层次遍历
- 二维数组中路径遍历
BFS 需要注意的点：
- 用队列存储（队列初始值即为BFS开始的节点）
- 用一个单独的数组记录遍历过的路径，避免重复节点入队（二叉树不用存储，因为二叉树是单向的）
- 用变量step存储走的路径（二叉树的最大or最小深度）
- 一般在出队列的时候判断是否为要搜索的目标，在入队列的时候判断是否遍历过
当从队列中取出一个节点时，此时
- 先要判断该节点是否为目标，
- 接着找到从该节点出发下一步搜索的范围（诸多节点），并判断之前是否搜索过，若没有则将其存到队列中
例如单词接龙中，从队列取出一个单词后，先判断是否为目标单词，判断不是目标后，则从该单词出发，寻找下一轮搜索的诸多单词。二叉树因为下一轮搜索范围必定为子节点，所以直接将子节点存放到队列即可。
多源BFS vs 单源BFS 总结
对于 「Tree 的 BFS」 （典型的「单源 BFS」）：
- 首先把 root 节点入队，再一层一层无脑遍历就行了。
对于 「图 的 BFS」 （「多源 BFS」） 做法其实也是一样的，与 「Tree 的 BFS」的区别：
- Tree 只有 1 个 root，而图可以有多个源点，所以首先需要把多个源点都入队；
- Tree 是有向的因此不需要标识是否访问过，而对于无向图来说，必须得标志是否访问过哦！并且为了防止某个节点多次入队，需要在其入队之前就将其设置成已访问！
模板
def BFS(G, V): # 将初始节点入队，且标记为已遍历状态 queue = deque() queue.append(V) visited = set() visited.add(V) # 记录扩散的步数 step = 0 while queue: sz = len(qqueue) step += 1 while sz > 0: cur_node = queue.popleft() sz -= 1 # 在出队的时候判断是否为目标 if cur_node is target: return step # 将 cur_node 的 相邻且未遍历节点 入队 for x in G[cur_node]: if x not in visited: visited.add(x) queue.append(x) return -1
树的层次遍历
在二叉树专题中有总结。
经典题目
图中节点的搜索
在图中一般是查找最短路径 以及 按照BFS的搜索路径做一些操作(542. 01矩阵 & 1675.地图中的最高点)
双向BFS
注意对简单BFS的优化：双向BFS。从起点和终点同时扩散，当遇到交集时停止，例127，752
双向BFS，一般是判断当前节点的邻居节点是否在对面的队列中，如果在，那么返回res + 1，为什么要 + 1 呢？ 因为邻居节点在对面，是邻居而不是当前节点，所以还需要一步。
也正是因为判断的是当前节点的邻居节点，所以在出队列的时候不判断，而是在找到邻居节点之后判断。
双向BFS需要两个队列，一个从起点，一个从终点。此外，还需要一个额外的队列，来存放每轮遍历队列的的邻居。所以，一共三个队列。（因为每次都是判断当前节点的邻居是否在对面，所以一般采用haseset，而不是数组。）
还需要一个hashset，来存放遍历过的节点
在矩阵中搜索
可能为多源BFS， 也可能为单源。谨记BFS 每一步都是将周围未遍历的节点添加到队列中。
经典题型
787 · 迷宫 - LintCode 对应🔒Leetcode 490
788 · 迷宫II - LintCode 对应🔒Leetcode 505
lintcode 789 https://www.lintcode.com/problem/789 迷宫Ⅲ 求到达目标位置的具体路径走法
lintcode 1685 https://www.lintcode.com/problem/1685 迷宫 Ⅳ 迷宫中多了干扰的东西
广泛搜索问题
BFS + 优先队列
其实就是 Dxxx 算法。
拓扑排序
拓扑排序：是有向无环图的所有顶点的线性序列。该序列满足以下两个条件：
- 每个顶点只出现一次
- 若存在一条从顶点A到顶点B的路径，那么A应该出现在B的前面
总结
- BFS DFS的时间复杂度均为O(n)
- BFS最擅长解决哪类问题？BFS与DFS的效率哪个更好？
- 首先BFS最谊长解决哪类问题？BFS是用来搜索最短径路的解是比较合适的 比如求最少步数的解，最少交换次数的解。因为BFS搜索过程中遇到的解一定是离根最近的，所以遇到一个解一定就是最优解。此时搜索算法可以终止。这个时候不适宜使用DFS，因为DFS搜索到的解不一定是离根般近的，只有全局搜索完毕才能从所有解中找出离根的最近的解。
- DFS是空间效率高。DFS不需要保存搜索过程中的状态。而BFS在搜索过程中需要保存搜索过的状态。而且一般情况需要一个队列来记录。详细来说的话，取决于树（图）的形状，扁的还是长条形
- DFS适合搜索全部的解。因为要搜索全部的解，那么BFS搜索过程中遇到离根最近的解 ，并没有什么用。DFS搜索也会搜索全部，但是相比BFS不用记录过多信息，所以搜素全部解的问题DFS显然史加合适
- 可以双向BFS优化搜索的速度进阶还会A* search