2
0
0
我能夠按照評論中InSync的建議解決了這個問題
在bfs()函數(shù)中，oldpath用于存儲每個節(jié)點(diǎn)（父節(jié)點(diǎn)）所經(jīng)過的路徑，shortest path用于存儲結(jié)果
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);
}
}
}
}
新函數(shù)的作用很簡單，將父節(jié)點(diǎn)添加到shortestPath中，然后找到父節(jié)點(diǎn)的父節(jié)點(diǎn)（如果存在），循環(huán)在當(dāng)前父節(jié)點(diǎn)為根節(jié)點(diǎn)時退出
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
}
}
不要將節(jié)點(diǎn)標(biāo)記為已訪問，而是利用這個機(jī)會將該節(jié)點(diǎn)與其父節(jié)點(diǎn)標(biāo)記。您可以使用一個 Map 來：
我還建議在函數(shù)中避免引用全局變量，而是將所有需要的內(nèi)容作為參數(shù)傳遞：
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);
