js广度优先遍历怎么实现

广度优先遍历（BFS，Breadth-First Search）是一种非常常见的图遍历算法，用于查找和遍历图中的所有节点。 这是一种迭代算法，就像深度优先遍历一样，但是广度优先遍历关注的是节点的位置而不是节点的深度。 这种算法的一般步骤是基于图中的节点和图的依赖结构从上到下访问所有节点。

广度优先遍历从图中的根节点开始处理，并通过将其所有相邻的节点加入到队列中的方式扩展其子级的范围。 每次通过队列处理一个节点时，首先检查它是否已被标记，然后将其标记并处理所有子节点，然后将其子节点全部加入队列中，以便之后逐个处理。

下面介绍两种实现 js 广度优先遍历的方法。

## 方法一：使用队列实现

步骤：

- 创建队列作为数据结构，并将起始节点添加到队列中。

- 创建一个数组，用于存储节点的值，并将起始节点的值加入其中。

- 取出 个节点并检查其所有相邻的节点。

- 如果这些节点当前尚未被标记，则将它们的值添加到数组中，并将它们添加到队列中。

- 重复上述步骤直到队列为空。

function bfs(root) {
  const queue = [root], // 创建队列
        res = [root.val] // 存放节点值的数组
  while(queue.length) { // 当队列不为空时
    const target = queue.shift() // 取出队头节点
    target.left && (res.push(target.left.val), queue.push(target.left)) // 处理左子树
    target.right && (res.push(target.right.val), queue.push(target.right)) // 处理右子树
  } 
  return res // 返回节点数组
}

## 方法二：递归实现

这种实现方法需要使用一个数组来记录每个层次节点的值。

步骤：

- 从根节点开始遍历，将其值添加到结果数组的 层。

- 从根节点开始遍历，递归访问它的子节点，并将门的值添加到结果数组的下一层。

- 重复上述步骤直到到达叶节点。

function bfs(root, res = [], level = 0) {
  if (!root) return [] // 如果根节点为空，则返回空数组
  if (!res[level]) res[level] = [] // 如果res[level]不存在，则创建
  res[level].push(root.val) // 存放节点的值
  root.left && bfs(root.left, res, level + 1) // 处理左子树
  root.right && bfs(root.right, res, level + 1) // 处理右子树
  return res.flat() // 返回节点数组
}

这样就可以使用两种方法之一来实现广度优先遍历了。这些方法适用于任何树结构，并且可以很容易地修改为支持图结构的遍历。