程式的目標是通過各個機場，並使用廣度優先搜尋演算法輸出PHX和BKK之間的最短路徑。 然而，我在列印結果方面遇到了困難。
預期輸出（最短路徑）為：PHX -> LAX -> MEX -> 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); // 將起始節點加入到已存取清單中 const queue = [start]; while (queue.length > 0) { const airport = queue.shift(); // 改變佇列 const destinations = adjacencyList.get(airport); for (const destination of destinations) { if (destination === 'BKK') { console.log(`BFS找到了曼谷！`) //console.log(path); } if (!visited.has(destination)) { visited.add(destination); queue.push(destination); } } } } 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);