前言
BFS和DFS是如影随形的两种搜索方式，我们在上篇文章从三道leetcode掌握深度优先搜索（DFS）学习了递归的概念及DFS。不熟悉递归及DFS的同学可以先看看上篇文章，再阅读本篇比较好。
BFS
BFS和DFS的区别在于
DFS是一条路走到黑，先搜索到最深层再返回上层进行搜索。BFS则是层层递进，先搜索当前所有数据再进行下一层搜索。
- 以上图为例，我们来看看使用
BFS的遍历顺序吧
- 从第一层开始搜索到单节点
A - 第二层搜索得到路径
B -> C -> D - 第三层搜索得到路径
E -> F -> G -> H - 同理继续下层搜索，最好完整路径为
A -> B -> C -> D -> E -> F -> G -> H -> I -> J -> K
1.二叉树的层序遍历
我们先来个简单的二叉树遍历
给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。
/** * Definition for a binary tree node. * function TreeNode(val, left, right) { * this.val = (val===undefined ? 0 : val) * this.left = (left===undefined ? null : left) * this.right = (right===undefined ? null : right) * } */ /** * @param {TreeNode} root * @return {number[][]} */ var levelOrder = function(root) { if (!root) return [] // 首先定义答案遍历 const ans = [] // 我们的BFS函数 // 可以发现BFS和DFS的变量不同 // BFS参数为数组，因为我们是整层整层搜索 const BFS = (nodes) => { // BFS出口 if (!nodes.length) return // 我们需要通过额外数组保存下一层的数据传给下一层搜索 const next = [] const layser = [] // 对当前层进行迭代搜索 for (let i = 0, len = nodes.length; i < len; i++) { const node = nodes[i] layser.push(node.val) // BFS的重点就是在于不会直接递归子节点数据 // 而是通过数组的方式来保存下层数据 // 在此层只处理此层数据达到层次分明 if(node.left) { next.push(node.left) } if (node.right) { next.push(node.right) } } ans.push(layser) // 递归下层数据 BFS(next) } // 数组形式的参数 BFS([root]) return ans }; 复制代码
2.岛屿的最大面积
我们在上篇文章通过DFS解答了此题，现在我们在通过BFS来解答此题，大家可以对比下两种方式的实现区别。
给你一个大小为 m x n 的二进制矩阵 grid 。
岛屿是由一些相邻的1(代表土地) 构成的组合，这里的「相邻」要求两个 1 必须在 水平或者竖直的四个方向上 相邻。你可以假设grid 的四个边缘都被 0（代表水）包围着。
岛屿的面积是岛上值为 1 的单元格的数目。
计算并返回 grid 中最大的岛屿面积。如果没有岛屿，则返回面积为 0 。
var maxAreaOfIsland = function(grid) { // m/n用于对比边界 const m = grid.length const n = grid[0].length // 定义输出变量 let ans = 0 // BFS函数 // 参数同样为数组 const BFS = (grids) => { // BFS出口 if (!grids.length) return 0 const nextGrids = [] let count = 0 // 处理当前层 for (let i = 0, len = grids.length; i < len; i++) { const [row, col] = grids[i] // 剪枝 if (grid[row][col] === 1) { // 将数据累加到当前层 count++ grid[row][col] = 0 // 将下层数据存储待下层函数使用 if (row > 0) { nextGrids.push([row - 1, col]) } if (row + 1 < m) { nextGrids.push([row + 1, col]) } if (col > 0) { nextGrids.push([row, col - 1]) } if (col + 1 < n) { nextGrids.push([row, col + 1]) } } } // 返回累计值 return count + BFS(nextGrids) } // 二维数组没有根节点 // 所以得遍历每个格子以此来进行上下左右的BFS搜索 for (let i = 0; i < m; i++) { for (let j = 0; j < n; j++) { if (grid[i][j] === 1) { // 比较更新答案 ans = Math.max(BFS([[i, j]]), ans) } } } return ans }; 复制代码
3. 01矩阵
我们再来看一个专为BFS定制的题
给定一个由 0 和 1 组成的矩阵 mat，请输出一个大小相同的矩阵，其中每一个格子是 mat 中对应位置元素到最近的 0 的距离。
两个相邻元素间的距离为 1。
本题初看是个很常规的递归搜索题型，可以使用BFS及DFS来搜索节点到最近0的距离。如果使用DFS来搜索的话，我们需要递归寻找直到搜索到0，但是此时的距离并不是简单的子节点（上下左右）距离+1，而是得通过横向对比来取最小值+1，而为了避免重复寻找，我们又需要去做去重处理，所以最后算法会变得非常复杂。
而使用BFS则很适合求解此类题型，我们称之为多源最短路径。
我们本要求解1到0的距离，我们反向思考，通过0来更新周围1的距离。通过同步更新0周围的1距离，比如最先更新0相邻的1,第二步更新与1相邻的1，这样通过层层外溢的搜索就可以确定最短距离了，而且是直接可以确定，不需要对比和更新，我们只需要避免重复更新就行。
var updateMatrix = function(mat) { const ans = [] // 边界m/n const m = mat.length const n = mat[0].length // 多源最短路径的源 const queue = [] // 上下左右方向 const dirs = [ [1, 0], [-1, 0], [0, 1], [0, -1] ] // BFS函数 const BFS = (grids) => { // BFS出口 if (!grids.length) return // 下一层数据 const next = [] // 本层数据搜索 for (let i = 0, gridsLen = grids.length; i < gridsLen; i++) { const [row, col] = grids[i] // 上下左右方向寻找下层数据 for (let i = 0, len = dirs.length; i < len; i++) { const dir = dirs[i] const x = row + dir[0] const y = col + dir[1] if (x >= 0 && y >= 0 && x < m && y < n && ans[x][y] === undefined) { ans[x][y] = ans[row][col] + 1 next.push([x, y]) } } } // 递归处理下层数据 BFS(next) } for (let i = 0; i < m; i++) { ans[i] = [] for (let j = 0; j < n; j++) { if (mat[i][j] === 0) { queue.push([i, j]) // 我们仅将源（0）加入ans // 这样未更新的就为undefined // 我们以此来去重 ans[i][j] = 0 } } } BFS(queue) return ans }; 复制代码
BFS的非递归实现
前面我们的BFS函数都是通过递归调用自身来实现的，我们在处理完本层数据之后，再调用自身处理下层数据，直到遇到出口为止。相对于DFS来说，递归调用是非常明确的，总是从n -> n +1，所以我们也可以通过队列的方式来实现。
其大致实现原理如下：
我们设置全局队列 queue，然后往队列中加入第一层数据
const quque = [] queue.push(1) 复制代码
然后再不断地遍历 queue，将得到的下层数据再加入队列
queue.push(2) // [1, 2] queue.push(2) // [1, 2, 2] 复制代码
可以发现，下一层的数据总是在本层后面，以此达到层次遍历。
我们以上面的第三题为例
var updateMatrix = function(mat) { const ans = [] const m = mat.length const n = mat[0].length const queue = [] const dirs = [ [1, 0], [-1, 0], [0, 1], [0, -1] ] for (let i = 0; i < m; i++) { ans[i] = [] for (let j = 0; j < n; j++) { if (mat[i][j] === 0) { queue.push([i, j]) ans[i][j] = 0 } } } // 我们通过全局队列来保存搜索节点 // 通过不断地前进搜索来实现BFS while(queue.length) { // 通过队列操作弹出第一个数据 const grid = queue.shift() const [row, col] = grid for (let i = 0, len = dirs.length; i < len; i++) { const dir = dirs[i] const x = row + dir[0] const y = col + dir[1] if (x >= 0 && y >= 0 && x < m && y < n && ans[x][y] === undefined) { ans[x][y] = ans[row][col] + 1 // 我们下层数据加入队列 queue.push([x, y]) } } } return ans }; 复制代码
我们可以仔细对比其中两种实现方式的差异，以后使用哪种方式都可以，全凭个人喜好。
BFS模板
通过上面的练习，我们来总结下BFS模板
- 递归模式
const BFS = (list) => { // 出口 if (!list.length) return // 下层数据数组 const next = [] for (let i = 0; i < list.length; i++) { // 处理当前节点 // 收集下层数据 next.push(node.child) } // 递归调用下层数据 BFS(next) } 复制代码
- 队列模式
const fn = () => { // 设置全局队列 const quque = [] // 加入第一层节点 queue.push(...) // 遍历数据 while(queue.length) { // 不断弹出首节点来达到清空队列得到出口 const node = quque.shift() // 处理当前节点 // 添加下层节点 queue.push(node.child) } } 复制代码
总结
我们来总结下本篇文章的知识点
BFS和DFS是两种常见的搜索方式，一种深度优先不撞南墙不回头，另一种广度优先层层递进BFS有两种实现方式，队列方式及递归方式BFS的一样需要设置函数出口防止无限循环或无限递归BFS比DFS更加适用于多源最短路径的题型BFS的常见模板
