什么是 BFS？
Breadth First Search (BFS) 宽度优先搜索，又称广度优先搜索，是图搜索算法中的一种，与 Depth First Search (DFS) 深度优先搜索一起，是面试中非常高频且重要的算法之一。
BFS 顾名思义，我们搜索的过程是平铺开进行搜索，即从起点开始，将所有和它相邻的结点都搜索一遍，然后再一个个去搜索这些相邻结点自己的相邻节点，一层一层铺开，从而进行搜索。其搜索过程就像水中的涟漪，从中心开始，向四周进行扩散，直到遍历完整个图。
BFS 为什么需要队列？
对于 BFS 算法，正如上面所说的，我们需要一层一层遍历所有的相邻结点。那么相邻结点之间的先后顺序如何确定？因此我们需要一个数据结构来进行存储和操作，需要使得先遍历的结点先被存储，直到当前层都被存储后，按照先后顺序，先被存储的结点也会被先取出来，继续遍历它的相邻结点。
<figcaption>图上的 BFS 搜索</figcaption>
因此我们可以发现，这个需求不就是我们的队列吗，First In First Out (FIFO) 完全契合这里的 use case。因此对于 BFS 我们需要使用 Queue 这样的一个数据结构，来存储每一层的结点，同时维护『先进先出 FIFO』的顺序。
BFS 算法过程
BFS 的实现过程也非常直接，主要由 3 部分组成：
- 起始：将起点（源点，树的根节点）放入队列中
- 扩散：从队列中取出队头的结点，将它的相邻结点放入队列，不断重复这一步
- 终止：当队列为空时，说明我们遍历了所有的结点，整个图都被搜索了一遍
下面我们以二维图的 BFS 搜索过程，详细图解讨论一下 BFS 的过程。
2D Matrix 上的 BFS
一般二维图会用 2D Matrix 来表示，我们可以将二维矩阵进行抽象 modelling：
- 将每一个元素看作结点（Vertex）
- 每一个元素和相邻的上下左右四个方向的元素中间有一条边（Edge）
因此，我们将矩阵上的搜索转换为图上的搜索。
对于这个图，是一个简单图，每一条边的权重 weight 都是 1，且每条边都是无向边。对于简单图，我们可以用 BFS 来寻找最短路径的长度。下面我们以这副图为例，来看一下我们如何通过 BFS 来找到起始点 1 到终点 9的最短距离。
为了避免歧义，这里注释一下。图中黄色表示已经搜索遍历过的结点，红色表示现在正在搜索的结点，粉色表示当前层的结点，绿色表示从当前层结点出发搜索到的相邻结点，即下一层的结点。下面我们来图解一下整个过程。
初始化搜索
首先，queue.offer(M[0][0]) 我们先将起始点加入空队列中，同时我们初始化我们的层数 level = 1，开始第一层的搜索。
接下来按照算法，我们需要不断从队首取出来元素，然后去搜索它的相邻结点。
第 0 层的搜索
首先通过 queue.poll() 得到当前的结点。
接下来将 M[0][0] 的上下左右四个相邻结点加入到队列中：
由于 1 的左和上都会出界，没有元素，因此添加完 2 和 7 后，就完成了当前层的搜索。此时 level 为 1，表示 2 和 7 距离起点 1 只有 1 层，距离为 1。更新层数 level++。
现在我们处理完了第 0 层的结点，要开始处理第一层的结点。但是由于在第二层时我们还会在『找邻居』的过程中找到第一层的结点，加入队列，从而进行了重复搜索，因此我们需要一种方法来标记某些结点被访问过。
一般我们使用一个和矩阵相同大小的二维 boolean array visited 来进行 mark。每次找到一个邻居时，先标记该位置为『已访问过』，visited[x][y] = true，再将邻居放入队列中。
第 1 层结点的搜索
接下来我们发现了另一个问题，对于第 0 层只有一个结点，我们不需要注意。但是现在第 1 层有两个结点，我们如何知道队列中哪些是第 1 层的结点，哪些是搜索得到的下一层的结点呢？
int size = queue.size()
我们可以在搜索当前层之前，获得当前队列的大小，因为当前状态下队列中的元素都是当前层的结点。通过队列的 size 进行限制，从而将当前层 poll 的次数限制在 size 次，从而区分开当前层和下一层的结点。
将 2 的相邻结点 3 和 8 放入队列，1 由于已经访问过了，不会再加入队列中。
接下来处理当前层的第二个结点 7，由于 7 也是当前层的最后一个结点，因此当它被从队列中 poll 出来后，队列中就全都是下一层的结点了。
由于 8 已经被访问过了，也不会再重复放入队列中，当把 13 放入队列后，当前层的搜索也已经结束。此时 level = 2 表示 2 和 7 到起点的距离是 2，更新层数 level++。
结束
对于最后一层，我们从 3 开始搜索邻居，当我们遇到 9 的时候，我们找到了终点，因此搜索结束。
此时 level 值为 3，表示终点 9 到起点 1 的距离为 3，也就是我们最后的答案。
对于整个搜索过程可以看下面的视频：
<iframe title="video" src="https://video.zhihu.com/video/1361277881042296833?player=%7B%22shouldShowPageFullScreenButton%22%3Atrue%7D" allowfullscreen="" class="css-uwwqev" frameborder="0"></iframe>
BFS搜索过程
代码
下面来看一下代码，正如我们前面所讨论的，我们使用了 size 以及 level 两个变量来维护搜索过程中的当前层以及当前层到起点的距离，以及使用 visited 数组进行标记访问过的结点避免重复访问。
代码非常简单，一目了然：
这里我们使用了自定义的 Class Cell 来表示每一个结点的横坐标和纵坐标，我们也可以使用一个长度为 2 的数组来表示，index 0 表示 x，index 1 表示 y。
