如何用BFS（Javascript）重建骑士棋子的最短路径？

Question

我目前正在与 TOP 合作开展一个项目，我被要求在 8x8 棋盘上找到两个有骑士的方格之间的最短路径。想象一下我想从 0,0 到 7,7，我的算法需要返回最短路径，所有访问过的方块都相对于这条最短路径。

对于这个项目，我创建了一个带有邻接列表对象的图形类。我创建了 addEdge 和 addVertex 函数以及 populateGraph 和 populateEdge 函数。

populateGraph 创建从 00 到 77 的顶点作为邻接列表的属性，并且 populateEdges 遵循国际象棋游戏中的骑士移动规则为所有属性创建边。

有了这个，我可以创建一个带有 2 个参数（ start 和 end ）的 BFS 函数，它会告诉我从开始到结束之前的移动次数。

为此，我创建一个以源作为第一个元素的队列，并创建一个访问集和骑士移动计数器为 0。

当我的队列不为空时，我获取队列的第一个元素，如果它已被访问，它将循环直到一个新元素，否则如果这个元素是我的末尾，我返回我的移动数，否则我增加我的 KnightMove ，将这个元素放入我访问过的 Set 中，并取出他的子元素并将它们推入队列。

为了达到 0.0 到 7.7，我需要 63 步。要从 0.0 移动到 1.2，我需要移动一步。

我想一旦找到结束节点，我就可以通过处理所有访问过的方块来重建路径，但我不知道如何做到这一点，也不知道这是否是一个好的解决方案。

这是我的 BFS :

js
 bfs(source, destination) {
    const queue = [source];
    const result = [];
    const visited = new Set();
    let knightMoves = 0;
    while (queue.length !== 0) {
      let max = queue[0];
      for (let i = 0; i < queue.length; i += 1) {
        if (queue[i] > max) {
          max = queue[i];
        }
      }
      let current = max;

      while (visited.has(current)) {
        current = queue.shift();
      }
      console.log(visited);
      if (current === destination) {
        console.log('Ive found the position.');
        console.log(`This is number of moves before found : ${knightMoves}`);
        return;
      }
      knightMoves += 1;

      visited.add(current);

      const neighbor = this.adjacencyList[current];

      neighbor.forEach((value) => {
        if (visited.has(value)) {
          return;
        }

        queue.push(value);
      });
    }
  }

Answer 1

您可以简单地存储移动到每个其他方格的方格的坐标。然后可以逆向重建路径。或者，您可以运行 DFS，在其中跟踪当前路径。

处理此问题的代码的简化版本：

const from = {}, dist = {};
dist[source] = 0;
while (queue.length && !(destination in from)) {
    const current = queue.shift();
    for (const next of this.adjacencyList[current]) {
        if (!(next in from)) {
            from[next] = current;
            dist[next] = dist[current] + 1;
            queue.push(next);
        }
    }
}
console.log('Number of moves:', dist[destination]);
const path = [];
for (let curr = destination; curr != null; curr = from[curr])
    path.push(curr);
// Now iterate in reverse to print the path

请注意，使用数组作为队列是一个非常糟糕的主意：从前面删除需要线性时间，而不是恒定时间。