How to get console.log('found it!') for Breadth First Search Traversal Using Graph Node 'BKKK'

Question

Trust you doing great,I am using below Graph traversal using Node.js to find all edges or routes for airport named BKKK

But somehow code is not showing the console.log('found it!') In code i am passing BreadthFirst search function and passing the start Node as 'PHX'

Can someone let me know what is going wrong in below code,why console.log('found it!') is not displayed while compiling the code?

            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);
            routes.forEach(route => addEdge(...route));





            console.log(adjacencyList);

            //BFS Breadth First Search 

            function bfs(start){

            const visited = new Set();

            const queue = [start]

            while (queue.length > 0) {

            const airport = queue.shift();
            const destinations = adjacencyList.get(airport);

            for(const destination of destinations){



            if(destination === 'BKKK'){

            console.log('found it!');

            if(!visited.has(destination)){

            visited.add(destination);
            queue.push(destination);
            }

            }

            }

            }

            }

            bfs('PHX');

Your help is highly appreciated

Regards

Carolyn

Answer 1

Here's the updated code that will work for you:

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);
routes.forEach(route => addEdge(...route));

console.log(adjacencyList);

//BFS Breadth First Search

function bfs(start) {
    const visited = new Set();

    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('found it!');
                break;
            }
            if (!visited.has(destination)) {
                visited.add(destination);
                queue.push(...adjacencyList.get(destination));
            }
        }
    }
}

bfs('PHX');

issues:

• you have a spelling mistake on line #49
• Since your addition to the destination queue is inside an if block which checks if the destination is the one you're looking for it will never reach because of the spelling mistake and even if it was fixed it will not solve the problem if the airports are not directly connected
• You're not adding all the possible destinations to the queue

Suggestions:

To make this code a bit more functional, it can be simplified to this:

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

const makeGraph = routes => {
    return routes.reduce((list, [origin, destination]) => {
        console.log(origin, destination);
        if (!list.get(origin)) {
            list.set(origin, []);
        }
        if (!list.get(destination)) {
            list.set(destination, []);
        }

        list.get(origin).push(destination);
        list.get(destination).push(origin);
        return list;
    }, new Map());
};

//find if there is a route between two airports
const findRoute = (graph, origin, destination) => {
    const queue = [origin];
    const visited = new Set();

    while (queue.length) {
        const airport = queue.shift();
        if (airport === destination) {
            console.log('found it!');
            break;
        }
        if (!visited.has(airport)) {
            visited.add(airport);
            queue.push(...graph.get(airport));
        }
    }
    return false;
};

const graph = makeGraph(routes);

findRoute(graph, 'PHX', 'BKK');