graph-implementation-bfs-dfs.js

// code of this video https://www.youtube.com/watch?v=cWNEl4HE2OE

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 adjacentLists = new Map()
function addNode(airport) {
    adjacentLists.set(airport, [])
}
// Add edge, undirected
function addEdge(origin, destination) {
    adjacentLists.get(origin).push(destination)
    adjacentLists.get(destination).push(origin)
}

// Create the graph
airports.forEach(addNode)
routes.forEach(route => addEdge(...route))

// console.log(adjacentLists)
// Graph search or traversal

// BFS breath first search
function bfs(start) {
    console.log("🚀 ~ file: graph-implementation-bfs-dfs.js ~ line 36 ~ bfs ~ start", start)

    const queue = [start]
    const visited = new Set();
    while (queue.length > 0) {
        const airport = queue.shift() // mutates the queue
        const destinations = adjacentLists.get(airport)
        for (const destination of destinations) {
            console.log(destination)
            if (destination === 'BKK') {
                console.log('Found it')
            }
            if (!visited.has(destination)) {
                visited.add(destination)
                queue.push(destination)
            }
        }
    }
}


// console.log(bfs('PHX'))

// DFS Depth First Search
function dfs(start, visited = new Set()) {
    console.log("🚀 ~ file: graph-implementation-bfs-dfs.js ~ line 61 ~ dfs ~ start", start)
    visited.add(start)
    const destinations = adjacentLists.get(start)
    for (const destination of destinations) {
        if (destination === 'BKK') {
            console.log(`DFS found in ${visited.size} steps`)
            return
        }
        if (!visited.has(destination)) {
            dfs(destination, visited)
        }
    }
}


console.log(dfs('PHX'))