javascript - 如何跟踪 BFS 图搜索 JavaScript 中的路径

Question

我正在研究 BFS 算法，但我很难弄清楚如何跟踪最短路径。
在我使用的代码下方:

const graph = {
  1: [2, 3, 4],
  2: [5, 6],
  3: [10],
  4: [7, 8],
  5: [9, 10],
  7: [11, 12],
  11: [13],
};

function bfs(graph, start, end) {
  let queue = [...graph[start]];
  let path = [start];
  let searched = [];
  while (queue.length > 0) {
    let curVert = queue.shift();
    if (curVert === end) {
      return path;
    } else if (searched.indexOf(curVert) === -1 && graph[curVert]) {
      queue = [...queue, ...graph[curVert]];
      searched.push(curVert);
      path.push(curVert);
    }
  }
}

console.log(bfs(graph, 1, 13));

函数调用的返回是最短路径。在这种情况下 [1, 4, 7, 11, 13]。

Answer 1

您还需要存储每个访问过的节点的路径。

const graph = { 1: [2, 3, 4], 2: [5, 6], 3: [10], 4: [7, 8], 5: [9, 10], 7: [11, 12], 11: [13] };

function bfs(graph, start, end) {
    let queue = [[start, []]],
        seen = new Set;

    while (queue.length) {
        let [curVert, [...path]] = queue.shift();
        path.push(curVert);
        if (curVert === end) return path;

        if (!seen.has(curVert) && graph[curVert]) {
            queue.push(...graph[curVert].map(v => [v, path]));
        }
        seen.add(curVert);
    }
}

console.log(bfs(graph, 1, 13));