BFS（Breadth First Search）是宽度优先搜索，又称广度优先搜索，一般在图，树以及矩阵的搜索中使用的比较多，对于图来说是优先访问所有和他相连的点，然后在访问更远的点……，对于树一般是一层一层的从上往下开始访问，而对于矩阵则是先访问当前位置的上下左右 4 个方向，然后再访问更远的位置。有种任人唯亲的感觉，就是谁离我近我就先访问谁，如下图所示。
如果在矩阵中，BFS 一般求连通区域以及最短距离相对来说比较多一些。在树中由于先从根节点往下访问，所以只需要使用一个队列就可以，但在图和矩阵中由于访问的方向不确定，会出现一个位置被多次访问然后出现死循环，解决方式也很简单，就是使用一个集合比如 Set，把访问过的位置（或者节点）添加进来，下次如果在到这个位置的时候首先判断有没有被访问过，如果被访问过就不在访问，否则就继续访问。当然除了使用集合以外我们还可以修改访问位置的值来做标记，但要注意有些时候访问完之后还要把当前位置的值给还原。
BFS 的使用模板
BFS 的实现原理就是优先访问最近的，一般配合着队列使用，因为队列是先进先出的，常见的一般有树，图和矩阵，我们来分别看下他们的实现过程以及大致使用模板（模板只是给我们提供了一个大致的解题轮廓以及解题思路，他并不能解决所有问题，还需要根据不同的题型来做不同的修改和调整，不要过分依赖模板）。
1，树的BFS使用模板
如下图所示，遍历树的时候，我们需要先把根节点添加到一个队列中，接着遍历队列中的节点（就是出队），然后判断这个节点还有没有子节点，如果有就加入到队列中，一直这样下去，直到队列为空为止。
结合上面的图我们来看下树的 BFS 遍历模板。
// 树的BFS遍历，实际上就是从上到下一层一层的打印。
public void bfsTree(Tree root) {
Queue<Tree> queue = new LinkedList<>();// 创建队列。
queue.offer(root);// 把开始查找的点放入到queue。
while (!queue.isEmpty()) {// 队列不为空就一直循环。
int levelCount = queue.size();// 可以理解为当前层节点的个数。
// 遍历当前层的所有点。
for (int i = 0; i < levelCount; i++) {
Tree cur = queue.poll();// 出队。
// 这里一般会有一些逻辑操作，比如计算res的值。
// 如果子节点不为空，就把子节点添加到队列中，对于二叉树来说只需要判断左右
// 子节点即可，如果是N叉树这里需要写个for循环，遍历当前节点的所有子节点。
if (cur.left != null)
queue.offer(cur.left);
if (cur.right != null)
queue.offer(cur.right);
}
// 或者这里有一些逻辑操作。
}
}
2，图的BFS使用模板
图的 BFS 遍历和树有一点区别的就是，在图的 BFS 遍历中我们需要使用一个集合或者数组来记录已经访问过的节点，防止一个点被重复访问导致错误或死循环。关于图的模板可以参考图的遍历。
3，矩阵的BFS使用模板
这个就更简单了，我们只需要访问每个位置的上下左右 4 个方向就行了，要注意访问的时候确保这 4 个方向不能越界，被访问之后还需要标记，防止重复访问，如下图所示。
假设从矩阵中的数字 6 开始访问，可以把它当做一棵 4 叉树，也就是说每个节点最多有 4 个子节点，访问的时候其实就是这棵树的 BFS 遍历。我们仔细观察就会发现一个重要的特点，比如树中节点 6 和节点 10 的高度相差 1 ，说明在矩阵中数字 6 至少需要走 1 步就可以到数字 10 。节点 6 和节点 3 的高度相差 2 ，说明在矩阵中数字 6 至少需要走 2 步就可以到数字 3 ，……。所以我们发现一个规律就是在矩阵中如果要计算从一个位置到另一个位置的距离，只需要在树中计算他俩的高度差即可。这个规律很重要，求最短路径的时候会经常用到，这里要注意在计算的时候，必须要以其中的一个位置为根节点来构造树，比如上面图中我们是以 6 为根节点构造的树，所以只能计算数字 6 到其他数字的距离，而不能计算其他任意两个数字的距离，而比如树中 5 和 8 的高度差是 1 ，因为这棵树不是以 5 或 8 作为根节点，所以在矩阵中 5 是不可能只需要一步就走到 8 ，模板如下。
// 从矩阵的某一个位置开始访问。
public void bfsGraph(int[][] matrix, int i, int j) {
// matrix为空这些条件大家自己判断，这里就不再写。
int m = matrix.length;
int n = matrix[0].length;
boolean[][] visited = new boolean[m][n];// 记录某个位置有没有被访问过。
Queue<int[]> queue = new LinkedList<>(); // 队列中记录的是位置的坐标值。
queue.offer(new int[]{i, j});// 先把起始位置加进来。
// 方向数组，计算当前位置的上下左右4个方向，原理很简单，对于数组nums[i][j]
// 来说，上下方向其实就是j不变，i减1和加1，对应的二维数组是{-1,0},{1,0}。
// 左右方向是i不变，j减1和加1，对应数组是{0，-1},{0,1}。
int[][] dirs = {{-1, 0}, {1, 0}, {0, 1}, {0, -1}};
// 如果队列不为空就一直循环。
while (!queue.isEmpty()) {
int[] position = queue.poll();// 出队。
// 遍历当前位置的上下左右4个方向。
for (int k = 0; i < 4; i++) {
int x = position[0] + dirs[k][0];
int y = position[1] + dirs[k][1];
// 访问矩阵的时候首先不能越界，如果越界直接跳过。
if (x < 0 || x >= m || y < 0 || y >= n)
continue;
// 如果被访问过了也要跳过，可以和上面的if语句合并，
// 这里为了讲解更清晰，故意拆开。
if (visited[x][y])
continue;
visited[x][y] = true;// 标记当前位置被访问过。
queue.offer(new int[]{x, y});// 然后把它加入到队列中。
}
}
}
