当前位置：首页 > JavaScript

js实现bfs

2026-02-01 00:32:00JavaScript

JavaScript 实现广度优先搜索（BFS）

广度优先搜索（BFS）是一种用于遍历或搜索树或图的算法，它从根节点开始，逐层访问所有相邻节点。以下是 JavaScript 实现 BFS 的几种常见方法。

基于队列的 BFS 实现

BFS 通常使用队列数据结构来实现，以下是针对树或图的通用实现方式。

树的 BFS 实现

假设树的节点结构如下：

js实现bfs

class TreeNode {
  constructor(val) {
    this.val = val;
    this.children = [];
  }
}

BFS 实现代码：

function bfsTree(root) {
  if (!root) return [];
  const queue = [root];
  const result = [];
  while (queue.length > 0) {
    const node = queue.shift();
    result.push(node.val);
    for (const child of node.children) {
      queue.push(child);
    }
  }
  return result;
}

图的 BFS 实现

对于图结构，需要使用一个 visited 集合来避免重复访问。

js实现bfs

function bfsGraph(startNode) {
  const queue = [startNode];
  const visited = new Set();
  visited.add(startNode);
  const result = [];
  while (queue.length > 0) {
    const node = queue.shift();
    result.push(node.val);
    for (const neighbor of node.neighbors) {
      if (!visited.has(neighbor)) {
        visited.add(neighbor);
        queue.push(neighbor);
      }
    }
  }
  return result;
}

处理层级信息

如果需要记录每一层的节点，可以通过以下方式实现：

function bfsWithLevels(root) {
  if (!root) return [];
  const queue = [root];
  const result = [];
  while (queue.length > 0) {
    const levelSize = queue.length;
    const currentLevel = [];
    for (let i = 0; i < levelSize; i++) {
      const node = queue.shift();
      currentLevel.push(node.val);
      for (const child of node.children) {
        queue.push(child);
      }
    }
    result.push(currentLevel);
  }
  return result;
}

应用场景示例

二叉树层级遍历
对于二叉树，BFS 可以用于按层输出节点值：

function levelOrder(root) {
  if (!root) return [];
  const queue = [root];
  const result = [];
  while (queue.length > 0) {
    const levelSize = queue.length;
    const level = [];
    for (let i = 0; i < levelSize; i++) {
      const node = queue.shift();
      level.push(node.val);
      if (node.left) queue.push(node.left);
      if (node.right) queue.push(node.right);
    }
    result.push(level);
  }
  return result;
}

最短路径问题
BFS 可以用于无权图的最短路径查找，例如网格中的最短路径：

function shortestPath(grid, start, end) {
  const queue = [[start, 0]];
  const visited = new Set([start.toString()]);
  const directions = [[1, 0], [-1, 0], [0, 1], [0, -1]];
  while (queue.length > 0) {
    const [[x, y], dist] = queue.shift();
    if (x === end[0] && y === end[1]) return dist;
    for (const [dx, dy] of directions) {
      const nx = x + dx, ny = y + dy;
      if (isValid(nx, ny, grid) && !visited.has([nx, ny].toString())) {
        visited.add([nx, ny].toString());
        queue.push([[nx, ny], dist + 1]);
      }
    }
  }
  return -1;
}