Gunakan algoritma BFS untuk meneroka graf dan keluarkan laluan terpendek

Question

Matlamat program ini adalah untuk melalui pelbagai lapangan terbang dan mengeluarkan laluan terpendek antara PHX dan BKK menggunakan algoritma carian pertama luas. Walau bagaimanapun, saya menghadapi masalah mencetak keputusan.

Keluaran yang dijangkakan (laluan terpendek) ialah: PHX ->

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

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


//Graf
const adjacencyList = Peta baharu();

//Tambah nod
function addNode(lapangan terbang) {
    adjacencyList.set(lapangan terbang, []);
}

// Tambah tepi, tidak terarah
fungsi addEdge(asal, destinasi) {
    adjacencyList.get(asal).push(destination);
    adjacencyList.get(destination).push(asal);
}

// Cipta Graf
airports.forEach(addNode);
// gelung melalui setiap laluan dan sebarkan nilai ke dalam fungsi addEdge
route.forEach(route => addEdge(...route));

Dengan nod sebagai titik permulaan (tapak) dan tepi sebagai destinasi, graf tidak terarah

function bfs(start) {
    const dilawati = new Set();
    visited.add(start); // Tambahkan nod permulaan pada senarai yang dilawati
    const queue = [mula];

    manakala (queue.length > 0) {

        const airport = queue.shift(); // tukar queue
        destinasi const = adjacencyList.get(lapangan terbang);

        untuk (destinasi const destinasi) {

            jika (destinasi === 'BKK') {
                console.log(`BFS jumpa Bangkok!`)
                //console.log(path);
                
            }

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

bfs('PHX')

Answer 1

Saya dapat menyelesaikan isu ini dengan mengikuti cadangan InSync dalam ulasan

Dalam fungsi bfs(), oldpath digunakan untuk menyimpan laluan yang dilalui oleh setiap nod (parent nod), dan laluan terpendek digunakan untuk menyimpan hasilnya

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

        }
    }
}

Fungsi fungsi baharu adalah sangat mudah Tambahkan nod induk ke shortestPath, kemudian cari nod induk nod induk (jika wujud), dan gelung keluar apabila nod induk semasa ialah nod akar

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

Daripada menandakan nod sebagai dilawati, gunakan peluang ini untuk menandai nod dengan induknya. Anda boleh menggunakan Peta untuk:

• Menunjukkan sama ada nod telah dilawati
• Menunjukkan nod sebelumnya (nod induk) sebelum mencapai
• Kekalkan susunan nod yang diakses dalam baris gilir

Saya juga mengesyorkan mengelakkan merujuk pembolehubah global dalam fungsi dan sebaliknya menghantar semua yang diperlukan sebagai parameter:

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