利用BFS演算法探索圖並輸出最短路徑
P粉633075725
P粉633075725 2023-09-03 11:42:48
0
2
627
<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>
P粉633075725
P粉633075725

全部回覆(2)
P粉232793765

我能夠按照評論中InSync的建議解決了這個問題

在bfs()函數中,oldpath用來儲存每個節點(父節點)所經過的路徑,shortest path用來儲存結果

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);
            }

        }
    }
}

新函數的作用很簡單,將父節點加入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
    }
}
P粉214176639

不要將節點標記為已訪問,而是利用這個機會將該節點與其父節點標記。您可以使用一個 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);
熱門教學
更多>
最新下載
更多>
網站特效
網站源碼
網站素材
前端模板
關於我們 免責聲明 Sitemap
PHP中文網:公益線上PHP培訓,幫助PHP學習者快速成長!