Graph Representation as Adjacency List

Graph Representation as Adjacency List.md

BFS & DFS Notes

Links

• Breadth-first search - Wikipedia
• Depth-first search - Wikipedia

Fundamentally a graph is a data structure which is characterized by nonlinearity for representing connections of vertices (or nodes) and edges. By definition:

A graph is a data structure which consists of a finite set of nodes (or vertices) with a set of edges connecting a pair of nodes (or vertices).

BFS and DFS are the inverse of the other, while BFS uses queue data structure, DFS uses stack data structure.

---

A graph can be represented as an adjacency matrix or adjacency list. In most cases, it is more efficient to use the latter because it requires less memory and offers better time-complexity when performing search algorithms.

Either search can be the best choice for a specific tree, graph, or problem. Generally, given an unweighted tree or graph, breadth first searches are preferred for situations where the desired node is likely to be closer (by number of levels) to the root.

graphTraversal.js

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

function bfs(start, end) {
  const visited = new Set([start]);
  const queue = [start];

  while (queue.length > 0) {
    const airport = queue.shift();
    const destinations = adjacencyList.get(airport);

    for (const destination of destinations) {
      if (destination === end) {
        console.log(`BFS found ${end} via ${airport}`);
      }

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

function dfs(start, end, visited = new Set()) {
  const destinations = adjacencyList.get(start);
  visited.add(start);

  for (const destination of destinations) {
    if (destination === end) {
      console.log(`DFS found ${end} from ${start}`);
      return;
    }

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

console.log('adjacencyList:', adjacencyList);

bfs('PHX', 'BKK');
dfs('PHX', 'BKK');