如何在 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));

我想在函数调用的return中得到的是最短路径。在这种情况下 [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));

Answer 2

对于每个顶点，保持其“前一个”顶点。由于没有回溯，一旦设置，前一个顶点就不会改变。同时，“previous”地图将跟踪已经访问过的顶点。当找到结束顶点时，向后迭代“先前”映射以计算路径。

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]
    let prev = {[start]: null}

    while (queue.length > 0) {
        let curr = queue.shift();

        if (curr === end) {
            let path = [];

            while (curr) {
                path.unshift(curr);
                curr = prev[curr];
            }

            return path;
        }

        if (curr in graph) {
            for (let v of graph[curr]) {
                if (!(v in prev)) {
                    prev[v] = curr;
                    queue.push(v);
                }
            }
        }
    }
}

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

如何在 BFS 图搜索中跟踪路径 JavaScript

How to keep track of path in BFS Graph search JavaScript

javascript

algorithm

breadth-first-search

shortest-path

ecmascript-6