利用BFS演算法探索圖並輸出最短路徑

Question

程式的目標是通過各個機場，並使用廣度優先搜尋演算法輸出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')

Answer 1

我能夠按照評論中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
    }
}

Answer 2

不要將節點標記為已訪問，而是利用這個機會將該節點與其父節點標記。您可以使用一個 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);