利用BFS演算法探索圖並輸出最短路徑
P粉633075725
2023-09-03 11:42:48
<p>程式的目標是通過各個機場,並使用廣度優先搜尋演算法輸出PHX和BKK之間的最短路徑。 <strong>然而,我在列印結果方面遇到了困難。 </strong></p>
<p>預期輸出(最短路徑)為:PHX -> LAX -> MEX -> BKK</p>
<pre class="brush:php;toolbar:false;">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));</pre>
<p>將節點作為起點(站點),邊作為目的地,該圖是無向的</p>
<pre class="brush:php;toolbar:false;">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')</pre></p>
我能夠按照評論中InSync的建議解決了這個問題
在bfs()函數中,oldpath用來儲存每個節點(父節點)所經過的路徑,shortest path用來儲存結果
新函數的作用很簡單,將父節點加入shortestPath中,然後找到父節點的父節點(如果存在),循環在目前父節點為根節點時退出
不要將節點標記為已訪問,而是利用這個機會將該節點與其父節點標記。您可以使用一個 Map 來:
我還建議在函數中避免引用全域變量,而是將所有需要的內容作為參數傳遞: