Verwenden Sie den BFS-Algorithmus, um das Diagramm zu untersuchen und den kürzesten Pfad auszugeben

Question

Ziel des Programms ist es, verschiedene Flughäfen zu durchqueren und mithilfe eines Breitensuchalgorithmus den kürzesten Weg zwischen PHX und BKK auszugeben. Ich habe jedoch Probleme beim Drucken der Ergebnisse.

Die erwartete Ausgabe (kürzester Pfad) ist: PHX -> LAX ->

const airports = 'PHX BKK OKC JFK LAX MEX EZE HEL LOS LAP LIM'.split(' ');

const Routen = [
    ['PHX', 'LAX'],
    ['PHX', 'JFK'],
    ['JFK', 'OKC'],
    ['JFK', 'HEL'],
    ['JFK', 'LOS'],
    ['MEX', 'LAX'],
    ['MEX', 'BKK'],
    ['MEX', 'LIM'],
    ['MEX', 'EZE'],
    ['LIM', 'BKK'],
];


//Der Graph
const adjacencyList = new Map();

//Knoten hinzufügen
Funktion addNode(Flughafen) {
    adjacencyList.set(airport, []);
}

// Kante hinzufügen, ungerichtet
Funktion addEdge(Ursprung, Ziel) {
    adjacencyList.get(origin).push(destination);
    adjacencyList.get(destination).push(origin);
}

// Das Diagramm erstellen
Flughäfen.forEach(addNode);
// Jede Route durchlaufen und die Werte in die Funktion addEdge verteilen
Routen.forEach(route => addEdge(...route));

Mit dem Knoten als Startpunkt (Standort) und der Kante als Ziel ist der Graph ungerichtet

function bfs(start) {
    const besuchte = new Set();
    besuchte.add(start); // Den Startknoten zur besuchten Liste hinzufügen
    const queue = [start];

    while (queue.length > 0) {

        const Airport = queue.shift(); // Warteschlange ändern
        const Destinations = adjacencyList.get(airport);

        for (const Ziel der Ziele) {

            if (destination === 'BKK') {
                console.log(`BFS hat Bangkok gefunden!`)
                //console.log(path);
                
            }

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

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