使用BFS算法遍历图后打印最短路径

Question

程序的目标是遍历各个机场，并使用广度优先搜索算法输出PHX和BKK之间的最短路径。然而，我在打印结果时遇到困难。

期望输出(最短路径)为:PHX ->宽松的→墨西哥人→BKK

const airports = 'PHX BKK OKC JFK LAX MEX EZE HEL LOS LAP LIM'.split(' ');
const routes = [
['PHX', 'LAX'], 
['PHX', 'JFK'],
['JFK', 'OKC'],
['JFK', 'HEL'],
['JFK', 'LOS'],
['MEX', 'LAX'],
['MEX', 'BKK'],
['MEX', 'LIM'],
['MEX', 'EZE'],
['LIM', 'BKK'],
];

// The graph
const adjacencyList = new Map();
// Add node
function addNode(airport) {
adjacencyList.set(airport, []);
}
// Add edge, undirected
function addEdge(origin, destination) {
adjacencyList.get(origin).push(destination);
adjacencyList.get(destination).push(origin);
}
// Create the Graph
airports.forEach(addNode);
// loop through each route and spread the values into addEdge function
routes.forEach(route => addEdge(...route));

以节点为原点(站)，以边为终点，图为无向

function bfs(start) {
const visited = new Set();
visited.add(start); // adding the starting node into the visited list
const queue = [start];
while (queue.length > 0) {
const airport = queue.shift(); // mutates the queue
const destinations = adjacencyList.get(airport);
for (const destination of destinations) {
if (destination === 'BKK')  {
console.log(`BFS found Bangkok!`)
//console.log(path);

}
if (!visited.has(destination)) {
visited.add(destination);
queue.push(destination);

}
}
}
}
bfs('PHX')

Answer 1

不要将节点标记为已访问，而是利用这个机会将该节点与其父节点标记在一起。您可以使用一个Map来:

• 访问节点
• 指示到达那里之前的节点(父节点)
• 以队列方式维护访问节点的顺序

我还会避免在函数中引用全局变量，而是将所有需要的作为参数传递:

function createGraph(airports, routes) {  // Your code, but as a function
// The graph
const adjacencyList = new Map();
// Add node
function addNode(airport) {
adjacencyList.set(airport, []);
}
// Add edge, undirected
function addEdge(origin, destination) {
adjacencyList.get(origin).push(destination);
adjacencyList.get(destination).push(origin);
}
// Create the Graph
airports.forEach(addNode);
// loop through each route and spread the values into addEdge function
routes.forEach(route => addEdge(...route));
return adjacencyList;
}

function bfs(adjacencyList, start, end) {
const cameFrom = new Map(); // Used as linked list, as visited marker, and as queue
cameFrom.set(start, null);
// As Map maintains insertion order, and keys() is an iterator,
//   this loop will keep looping as long as new entries are added to it
for (const airport of cameFrom.keys()) {
for (const destination of adjacencyList.get(airport)) {
if (!cameFrom.has(destination)) {
cameFrom.set(destination, airport); // remember parentNode
if (destination === end) return retracePath(cameFrom, end);
}
}
}
}
function retracePath(cameFrom, node) {
const path = [];
while (cameFrom.has(node)) {
path.push(node);
node = cameFrom.get(node);
}
return path.reverse();
}
const airports = 'PHX BKK OKC JFK LAX MEX EZE HEL LOS LAP LIM'.split(' ');
const routes = [
['PHX', 'LAX'], 
['PHX', 'JFK'],
['JFK', 'OKC'],
['JFK', 'HEL'],
['JFK', 'LOS'],
['MEX', 'LAX'],
['MEX', 'BKK'],
['MEX', 'LIM'],
['MEX', 'EZE'],
['LIM', 'BKK'],
];
const adjacencyList = createGraph(airports, routes); 
const path = bfs(adjacencyList, 'PHX', 'BKK');
console.log(path);

Answer 2

我按照InSync在评论中的建议解决了这个问题

bfs()中的代码:oldpath用于存储每个节点的路径(parentNode)最短路径用于存储结果

const oldpath = new Map();
let shortestPath = [];

while (queue.length > 0) {
let airport = queue.shift(); // mutates the queue
const destinations = adjacencyList.get(airport);
for (const destination of destinations) {
// destination -> origin
if (destination === 'BKK')  {
console.log(`BFS found Bangkok!`)
oldpath.set(destination, airport) // remember parentNode    
retracePath(airport);    // loops through all parentNodes of BKK 
//   and adds them to the path
console.log(shortestPath);
shortestPath = []
}
if (!visited.has(destination)) {
oldpath.set(destination, airport) // remember parentNode
visited.add(destination);
queue.push(destination);
}
}
}
}

新的函数任务很简单，将parentNode添加到shortesPath中，然后查找parentNode的父节点(如果存在)，当当前parentNode为根节点时退出循环

function retracePath(parentNode){
while(oldpath.get(parentNode)){ // keep going until reaching the root
shortestPath.unshift(parentNode); // adding each parent to the path 
parentNode = oldpath.get(parentNode); // find the parent's parent
}
}