使用BFS算法遍历图后打印最短路径的问题求助

程序目标是使用广度优先搜索（BFS）算法遍历各机场，输出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'],
];

// 图的邻接表
const adjacencyList = new Map();

// 添加节点
function addNode(airport) {
    adjacencyList.set(airport, []);
}

// 添加无向边
function addEdge(origin, destination) {
    adjacencyList.get(origin).push(destination);
    adjacencyList.get(destination).push(origin);
}

// 构建图
airports.forEach(addNode);
routes.forEach(route => addEdge(...route));

该图为无向图，节点代表机场，边代表机场间的航线。

现有BFS代码 #

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 found Bangkok!`)
                // console.log(path); 此处无法输出路径
            }

            if (!visited.has(destination)) {
                visited.add(destination);
                queue.push(destination);
            }
        }
    }
}

bfs('PHX')

问题原因 #

现有BFS只记录了已访问节点和待遍历队列，没有记录每个节点的前驱节点，因此找到BKK时无法回溯出从PHX到BKK的完整路径。

解决方法 #

修改BFS函数，新增一个predecessors Map来保存每个节点的上一个节点，找到BKK后从BKK反向回溯到PHX，再反转路径得到正序的最短路径：

function bfs(start, target) {
    const visited = new Set();
    const predecessors = new Map(); // 记录每个节点的前驱节点
    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 === target) {
                // 找到目标节点，回溯路径
                predecessors.set(destination, airport);
                const path = [];
                let current = target;
                while (current) {
                    path.unshift(current);
                    current = predecessors.get(current);
                }
                console.log(`最短路径：${path.join(' -> ')}`);
                return; // BFS特性保证首次找到即为最短路径，直接返回
            }

            if (!visited.has(destination)) {
                visited.add(destination);
                predecessors.set(destination, airport); // 记录前驱节点
                queue.push(destination);
            }
        }
    }
    console.log(`无法找到从${start}到${target}的路径`);
}

bfs('PHX', 'BKK')

输出结果 #

运行修改后的代码，会输出：

最短路径：PHX -> LAX -> MEX -> BKK

内容的提问来源于stack exchange，提问作者Abdelrahman Salah