The graph

The graph represent connections between airports. Nodes (vertices)  represent airports, and  edges represent flights.

BFS search (Breadth First Search)

Breadth-first Search (BFS) starts by pushing all of the direct children to a queue (first-in, first-out). It then visits each item in queue and adds the next layer of children to the back of the queue. Since one node could be visited multiple times causing infinite loop, we have to keep track of all visited nodes.

Using JavaScript Map

// DATA
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[0], route[1]));

console.log(adjacencyList);


function bfs(start, searchItem) {

    const visited = new Set();
    const queue = [start];


    while (queue.length > 0) {

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


        for (const destination of destinations) {
            if (destination === searchItem)  {
                console.log(`BFS found a route to`, searchItem)
            }

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

}

bfs('PHX', 'BKK');

Using JavaScript object

// Data
var airports = {
    'PHX': ['LAX', 'JFK'],
    'BKK': ['MEX', 'LIM'],
    'OKC': ['JFK'],
    'JFK': ['LAX', 'PHX', 'OKC', 'HEL', 'LOS', 'EZE'],
    'LAX': ['PHX', 'JFK', 'MEX'],
    'MEX': ['LAX', 'EZE', 'BKK', 'LIM'],
    'EZE': ['JFK', 'MEX'],
    'HEL': ['JFK'],
    'LOS': ['JFK'],
    'LAP': [],
    'LIM': ['MEX', 'BKK']
};


function bfs(start, endDest) {
    var queue = [start];
    var visited = {};

    while(queue.length > 0) {
        var curentNodeVal = queue.shift();
        var childNodes = airports[curentNodeVal];
        for(const childNode of childNodes) {
            if(childNode === endDest) {
                console.log("BFS found a route to :", endDest);
            }            

            if(!visited[childNode]) {
                console.log(childNode);
                visited[childNode] = true;
                queue.push( childNode);          
            }
        }
    }
}


bfs('PHX', 'BKK');

DFS (Depth First Search)

Depth-first Search (DFS) will go as far into the graph as possible until it reaches a node without any children, at which point it backtracks and continues the process. The algorithm can be implemented with a recursive function that keeps track of previously visited nodes. If a node has not been visited, we call the function recursively.

Using JavaScript Map

// DATA
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[0], route[1]));

console.log(adjacencyList);



function dfs(start, visited = new Set()) {

    console.log(start)
    
    visited.add(start);

    const destinations = adjacencyList.get(start);

    for (const destination of destinations) {

        if (destination === 'BKK') { 
            console.log(`DFS found Bangkok`)
            return;
        }
        
        if (!visited.has(destination)) {
            dfs(destination, visited);
        }

    }

}

dfs('PHX');

Using JavaScript object

// Data
var airports = {
    'PHX': ['LAX', 'JFK'],
    'BKK': ['MEX', 'LIM'],
    'OKC': ['JFK'],
    'JFK': ['LAX', 'PHX', 'OKC', 'HEL', 'LOS', 'EZE'],
    'LAX': ['PHX', 'JFK', 'MEX'],
    'MEX': ['LAX', 'EZE', 'BKK', 'LIM'],
    'EZE': ['JFK', 'MEX'],
    'HEL': ['JFK'],
    'LOS': ['JFK'],
    'LAP': [],
    'LIM': ['MEX', 'BKK']
};


function dfs(start, endDest, visited = {}) {
        
    visited[start] = true;
    console.log(start);

    const destinations = airports[start];

    for(const destination of  destinations) {
        if (destination === endDest) { 
            console.log(`DFS found route to`, endDest);
        }

        if(!visited[destination]) {
            dfs(destination, endDest, visited);
        }
        
    }
}


dfs('PHX', 'BKK');