利用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);