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

Answer 2

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

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));