Javascript - BFS Algorithmus - Route speichern?

Hey Leute,

ich versuche gerade einen Pathfinder umzusetzten, der mir am schluss eine (die beste) Route ausgibt, die er finden konnte. Dafür habe ich den BFS Algorithmus umgesetzt, der bereits auch den Weg findet.

Wie aber speicher ich die Route so, dass ich diese am Ende dem User anzeigen kann (z.B. Hauptbahnhof -> BushalteA -> BushalteB -> BushalteC)

Hier mein Code:

function bfs(start, searchFor){
    const vistited = new Set();
    const queue = [start];


    while(queue.length > 0){
        const busStop = queue.shift();
        const destinations = networkList.get(busStop);


        for (const destination of destinations){
            if(destination == searchFor){
                console.log("Connection from "+ start +" to "+ searchFor +" is possible");
                return;
            }


            if(!vistited.has(destination)){
                vistited.add(destination);
                queue.push(destination);
                console.log(destination);
            }
        }
    }
    console.log("No route found!");
}

Answer 1

[KarlRanseierIII]

Der typische Weg:

Bei der Suche speicherst Du mit jedem erreichten Knoten den Vorgänger von dem aus Du ihn erreicht hast. Dann kannst Du den Pfaf in umgekehrt Richtung zum Start zurücklaufen, z.B. auf nen Stack pushen und dann in umgekehrter Reihenfolge ausgeben. Fertig.