从三道leetcode掌握广度优先搜索（BFS）

/**
 * 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
};
复制代码

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
};
复制代码

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
};
复制代码

const quque = []
queue.push(1)
复制代码

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
};
复制代码

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)
  }
}
复制代码