graphSearch.js

/*  Graph Search Algoroithms
*  Here we would implement a graph in the form of an adjacency list
*  There are a few ways this can be done :
*  a.Adjacency Matrix: Represent each node in a 2D matrix, the edges represent relationships between nodes
*  b.Adjacency List: Start with a collection of nodes each having their array of edges, this is easier 0on memmory and faster
*  Adjacency matrix method is not desirable because adding, finding or working with nodes take an O(n^2) space and time complexity
*/

// Let's work with a graph connecting airports and their routes
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 = new Map();

// util
const addNode = airport => adjacencyList.set(airport, []);
const addEdge = (origin, destination) => {
  adjacencyList.get(origin).push(destination);
  adjacencyList.get(destination).push(origin);
};

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

// To see how the graph looks like:
console.log(adjacencyList);

// Graph search or Traversal
// For this we are going to use Breadth First Search ( this normally find mutliple routes)
const bfs = (startingNode, searchParam) => {
  const queue = [startingNode];
  const visited = new Set(); // we don't want to have  records of visiting the same destination twice
  while (queue.length > 0) {
    const airport = queue.shift();//get and remove the first item in the queue
    const destinations = adjacencyList.get(airport); // get the particular airpot routes
    for (const destination of destinations) {
      if (destination === searchParam) console.log(`Found ${searchParam}`);
      
      if (!visited.has(destination)) {
        visited.add(destination);
        queue.push(destination); // Add the destination to the queue only if it has not been visited
        console.log(destination);
      }
    }
  }
}

bfs('PHX', 'BKK');


// Trying depth-first search to (to find the fastest route)
const dfs = (startingNode, searchParam, visited = new Set()) => {
  console.log(startingNode);
  visited.add(startingNode);
  const destinations = adjacencyList.get(startingNode);
  for (const destination of destinations) {
    if (destination === searchParam) console.log(`Found ${searchParam}`);

    if (!visited.has(destination)) {
      dfs(destination, searchParam, visited);
    }
  }
}

dfs('PHX', 'BKK');