当前位置：首页 > JavaScript

js实现bfs

2026-04-05 16:53:06JavaScript

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

广度优先搜索是一种用于遍历或搜索树或图的算法，从根节点开始，逐层访问所有相邻节点。以下是 JavaScript 实现 BFS 的两种常见方式：基于队列的迭代实现和递归模拟实现。

基于队列的迭代实现

定义图结构
使用邻接表表示图，例如：

const graph = {
  A: ['B', 'C'],
  B: ['A', 'D', 'E'],
  C: ['A', 'F'],
  D: ['B'],
  E: ['B', 'F'],
  F: ['C', 'E']
};

BFS 核心逻辑
初始化队列和已访问集合，逐层扩展节点：

function bfs(startNode, graph) {
  const visited = new Set();
  const queue = [startNode];
  visited.add(startNode);

  while (queue.length > 0) {
    const currentNode = queue.shift();
    console.log(currentNode); // 处理当前节点

    for (const neighbor of graph[currentNode]) {
      if (!visited.has(neighbor)) {
        visited.add(neighbor);
        queue.push(neighbor);
      }
    }
  }
}

bfs('A', graph); // 从节点 A 开始遍历

递归模拟实现

虽然 BFS 通常用队列迭代实现，但可通过递归模拟队列行为：

function bfsRecursive(queue, visited, graph) {
  if (queue.length === 0) return;

  const currentNode = queue.shift();
  console.log(currentNode); // 处理当前节点

  for (const neighbor of graph[currentNode]) {
    if (!visited.has(neighbor)) {
      visited.add(neighbor);
      queue.push(neighbor);
    }
  }

  bfsRecursive(queue, visited, graph);
}

const visited = new Set(['A']); // 起始节点标记为已访问
bfsRecursive(['A'], visited, graph);

应用场景示例

最短路径问题
在无权图中，BFS 可找到两点间的最短路径。修改上述代码记录路径：

function bfsShortestPath(start, end, graph) {
  const queue = [[start, [start]]];
  const visited = new Set([start]);

  while (queue.length > 0) {
    const [currentNode, path] = queue.shift();
    if (currentNode === end) return path;

    for (const neighbor of graph[currentNode]) {
      if (!visited.has(neighbor)) {
        visited.add(neighbor);
        queue.push([neighbor, [...path, neighbor]]);
      }
    }
  }
  return null; // 无路径
}

console.log(bfsShortestPath('A', 'F', graph)); // 输出最短路径

层序遍历
记录每层的节点，适用于树或图的层级分析：

js实现bfs

function bfsLevelOrder(startNode, graph) {
  const result = [];
  const queue = [startNode];
  const visited = new Set([startNode]);

  while (queue.length > 0) {
    const levelSize = queue.length;
    const currentLevel = [];

    for (let i = 0; i < levelSize; i++) {
      const currentNode = queue.shift();
      currentLevel.push(currentNode);

      for (const neighbor of graph[currentNode]) {
        if (!visited.has(neighbor)) {
          visited.add(neighbor);
          queue.push(neighbor);
        }
      }
    }
    result.push(currentLevel);
  }
  return result;
}

console.log(bfsLevelOrder('A', graph)); // 输出按层分组的节点