我正在研究 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]
.