Graphs

A graph is a connection of nodes data structure. Each node is called a vertex and the connection between them are called edges.

Formally, a graph G=(V,E) is a finite set of vertices $V$ and a set of edges $E$. Each edge is a pair $(v, u)$ where $v$, $u$ are elements of $V$.

A graph can be represented in two ways:

• Adjacent Matrix: A 2-D array of size $V \times V$ where $V$ is the number of vertices in the graph and the value of an entry adj[i][j] is either 1 or 0. A value of 1 indicates that there is an edge from vertex i to vertex j, otherwise 0.

• Adjacent List: An array of list. In Javascript, this can be easily represented using an object of key-values, where the key is the node and the value are the nodes it is connected to. I would highly recommend using this representation for Graphs ✅.

It is also important to note that there are two types of graphs:

Directed Graphs

Edges have a direction.

V = {V1, V2, V3, V4}
E = {(V1, V2), (V2, V3), (V3, V2), (V4, V1)}

Undirected Graphs

Edges do not have a direction.

V = {V1, V2, V3, V4}
E = {(V1, V2), (V1, V3), (V2, V3), (V3, V4)}

From Edges to Adjacent List

Sometimes, we are given the edges of a graph in an coding interview. A good way to represent the graph is using an adjacent list.

// Given input of edges
const edges = [
  [0, 1],
  [1, 2],
  [2, 3],
  [3, 0],
  [2, 0]
];
 
function buildGraph(edges) {
  const graph = {}
 
  for (let [a,b] of edges) {
    if (!(a in graph)) graph[a] = [];
    if (!(b in graph)) graph[b] = [];
    graph[a].push(b);
    graph[b].push(a);
  }
 
  return graph
}
 
-> {
  0: [1, 3, 2],
  1: [0, 2],
  2: [1, 3, 0],
  3: [2, 0]
} 

Acylic Graphs

A graph with no cycles.

Depth First Search (DFS)

DFS is a graph traversal algorithm. It starts at the start node and explores as deep as possible along each branch before backtracking. We can implement DFS using a stack or recursion.

DFS Stack

function dfs(graph, source) {
  let stack = [source];
 
  while (stack.length > 0) {
    let current = stack.pop();
    
    console.log('Do something', current);
 
    for (let neighbor of graph[current]) {
      stack.push(neighbor);
    }
  }
}

DFS Recursively

function dfs(graph, source) {
 
  console.log('Do something', source);
 
  for (let neighbor of graph[source]) {
    dfs(graph, neighbor);
  }
}

Breadth First Search (BFS)

BFS is a graph traversal algorithm. It starts at the start node and explores all of its neighbors before moving on to the nodes at the next depth level. The only way to implement BFS is using a queue.

Queue BFS

Cylic Graphs

Depth First Search

Breadth First Search