如何用JavaScript的BFS算法重构国际象棋骑士的最短路径？

你的BFS核心问题 #

你的代码完全违背了BFS的核心逻辑，导致步数计算错误：

• 每次从队列中取最大值而非队首元素，彻底打乱了BFS的层级遍历顺序（BFS要求先进先出，保证按步数层级扩散）
• visited的处理逻辑混乱，反复shift队列直到找到未访问元素，导致节点重复处理、步数累加错误
• knightMoves的累加时机错误，每处理一个节点就加1，而非每完成一层遍历（一步）才加1

修正后的BFS实现（含路径回溯） #

要正确计算最短路径并重构路径，我们需要用父节点映射记录每个节点的前驱，找到终点后反向回溯出完整路径。以下是修正后的代码：

bfs(source, destination) {
  const queue = [source];
  const visited = new Set([source]);
  // 记录每个节点的父节点，用于回溯路径
  const parent = {};

  while (queue.length > 0) {
    const current = queue.shift();

    // 找到终点，开始重构路径
    if (current === destination) {
      const path = [];
      let node = destination;
      // 从终点反向遍历到起点
      while (node !== undefined) {
        path.unshift(node);
        node = parent[node];
      }
      console.log(`最短路径步数：${path.length - 1}`);
      console.log(`完整路径：${path.join(' -> ')}`);
      return path;
    }

    // 遍历当前节点的所有邻居
    const neighbors = this.adjacencyList[current];
    for (const neighbor of neighbors) {
      if (!visited.has(neighbor)) {
        visited.add(neighbor);
        parent[neighbor] = current;
        queue.push(neighbor);
      }
    }
  }

  // 棋盘内任意两点都可达，此为兜底逻辑
  return null;
}

关键逻辑说明 #

1. 严格遵循BFS顺序：每次取出队列队首元素，保证遍历按步数层级扩散，第一次到达终点时的路径就是最短路径
2. 父节点映射：parent对象记录每个节点的来源节点，找到终点后从终点反向遍历到起点，再反转数组得到从起点到终点的路径
3. 正确标记已访问：节点加入队列时就标记为已访问，避免重复入队，提升效率

比如测试(0,0)到(7,7)，会得到正确的最短路径（通常是6步左右，而非63步），(0,0)到(1,2)会直接返回步数1和对应路径。

内容的提问来源于stack exchange，提问作者Hachounet