Ziel des Programms ist es, verschiedene Flughäfen zu durchqueren und mithilfe eines Breitensuchalgorithmus den kürzesten Weg zwischen PHX und BKK auszugeben. Ich habe jedoch Probleme beim Drucken der Ergebnisse.
Die erwartete Ausgabe (kürzester Pfad) ist: PHX -> LAX ->
const airports = 'PHX BKK OKC JFK LAX MEX EZE HEL LOS LAP LIM'.split(' '); const Routen = [ ['PHX', 'LAX'], ['PHX', 'JFK'], ['JFK', 'OKC'], ['JFK', 'HEL'], ['JFK', 'LOS'], ['MEX', 'LAX'], ['MEX', 'BKK'], ['MEX', 'LIM'], ['MEX', 'EZE'], ['LIM', 'BKK'], ]; //Der Graph const adjacencyList = new Map(); //Knoten hinzufügen Funktion addNode(Flughafen) { adjacencyList.set(airport, []); } // Kante hinzufügen, ungerichtet Funktion addEdge(Ursprung, Ziel) { adjacencyList.get(origin).push(destination); adjacencyList.get(destination).push(origin); } // Das Diagramm erstellen Flughäfen.forEach(addNode); // Jede Route durchlaufen und die Werte in die Funktion addEdge verteilen Routen.forEach(route => addEdge(...route)); Mit dem Knoten als Startpunkt (Standort) und der Kante als Ziel ist der Graph ungerichtet
function bfs(start) { const besuchte = new Set(); besuchte.add(start); // Den Startknoten zur besuchten Liste hinzufügen const queue = [start]; while (queue.length > 0) { const Airport = queue.shift(); // Warteschlange ändern const Destinations = adjacencyList.get(airport); for (const Ziel der Ziele) { if (destination === 'BKK') { console.log(`BFS hat Bangkok gefunden!`) //console.log(path); } if (!visited.has(destination)) { besuchte.add(Ziel); queue.push(Ziel); } } } } bfs('PHX')
我能够按照评论中InSync的建议解决了这个问题
在bfs()函数中，oldpath用于存储每个节点（父节点）所经过的路径，shortest path用于存储结果
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); } } } }新函数的作用很简单，将父节点添加到shortestPath中，然后找到父节点的父节点（如果存在），循环在当前父节点为根节点时退出
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 } }不要将节点标记为已访问，而是利用这个机会将该节点与其父节点标记。您可以使用一个 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);