广度优先搜索精讲
什么是广度优先搜索？
广度优先搜索（英文:Breadth First Search，简称 bfs），又称宽度优先搜索，是一种搜索算法。顾名思义，就是更大范围内搜索，先访问完当前顶点的所有邻接点，然后再访问下一层的所有节点，该算法适用于解决最短、最小路径等问题。
广度优先搜索使用队列实现，每次将周围的邻接点加入队列，逐层搜索。
广度优先搜索因为其采用层级遍历，像洪水一样逐层扩散，无需重复访问、无需回溯，所以较深度优先搜索的指数级时间复杂度的效率有着显著提升。
广度优先搜索的原理和实现
广度优先搜索的步骤
广度优先搜索通过队列实现，将起始点加入队列，然后只要队列不为空，对于合法的邻接点加入队列，一层一层的进行遍历。
例如对于一个无向图，有 (1,2)(1,2)(1,2) ,(1,3)(1,3)(1,3) , (3,4)(3,4)(3,4), (2,4)(2,4)(2,4) 四条边。广度优先搜索的步骤如下：
* 定义一个队列 qqq，用于维护当前待处理的节点；
* 从 111 开始搜索，将 111 节点加入队列 qqq；
* 111 的邻接边有 (1,2)(1,2)(1,2) 和 (1,3)(1,3)(1,3) ，然后将节点 222 和 333 加入队列 qqq，将节点 111 退出队列；
* 然后对于节点 222 ，它的邻接边有 (1,2)(1,2)(1,2) 和 (2,4)(2,4)(2,4) ，因为节点 111 已被访问过，跳过，将节点 444 加入队列 qqq， 将节点 222 退出队列；
* 对于节点 333，它的邻接边有 (1,3)(1,3)(1,3) 和 (3,4)(3,4)(3,4) ，但是节点 111 和 444 都已被访问，跳过；
* 对于节点 444，它的邻接边有 (2,4)(2,4)(2,4) 和 (3,4)(3,4)(3,4)，但是节点 222 和 333 都已被访问过，跳过；
* 队列空了，遍历结束。
广度优先搜索模版代码
题目练习
迷宫类问题
A8036.走迷宫
这道题是一个经典的迷宫问题，相对与用 dfs 算法，bfs 算法效率更高。
这道题中，角色要在 n×mn \times mn×m 的地图里走路，每次只能向上下左右走 111 格，并且只有.的位置才能走。
对于这类题型，我们可以用 dx 和 dy数组记录运动轨迹，每次遍历 dx ， dy 数组，移动到对应位置。
注意：对于走迷宫类题型需要注意当前位置是否合法，即是否满足当前位置不越界，当前位置可以走。
代码：
预期分数： 100pts100pts100pts
时间复杂度： O(nm)\operatorname{O(nm)}O(nm)
空间复杂度：O(nm)\operatorname{O(nm)}O(nm)
连通块问题
A8040.细胞
本题目是一道经典的连通块问题。
这道题具有一定思维含量，可以通过循环遍历，对于每个不属于其他连通块的格子（visi,jvis_{i,j}visi,j === 000）通过 bfs 搜索确定大小并标记所属的格子，最后记录有多少个连通块。
代码：
预期分数：100pts100pts100pts
时间复杂度：O(nm)\operatorname{O(nm)}O(nm)
空间复杂度：O(nm)\operatorname{O(nm)}O(nm)
课后作业
必做
* 复习 dfs 的逻辑，找一找 bfs 和 dfs的不同之处。
* 将之前 dfs 的题想想可不可以用 bfs 优化
* 完成连通块问题，图的遍历，迷宫问题普及难度题目各 222 道
选做
* 分析对于不同题目下 bfs 的优化和时间复杂度，尝试利用剪枝等方法提升效率。
* 学习更多题型，练习 333 道以上，并借助题解理解他人解法；
* 做 101010 道搜索提高题
感谢大家的观看！
@AC君 我要加精华
