Graphs

How It Works

A graph is a collection of nodes (vertices) connected by edges, with no restriction that it be hierarchical or acyclic: any node can connect to any other node, cycles are allowed, and edges can be directed (one-way) or undirected (two-way), weighted or unweighted. A tree is technically a special case of a graph (connected, acyclic). Graphs model anything relational: social networks, road maps, dependency graphs, web page links, and state machines.

There are two standard ways to represent a graph in memory:

• Adjacency list: a map/array where each node stores a list of its neighbors. Space is O(V + E), and it's efficient for sparse graphs (few edges relative to nodes). This is the default choice in almost every interview.
• Adjacency matrix: a V x V grid where matrix[i][j] indicates an edge between i and j. O(V²) space regardless of edge count, but O(1) edge-existence checks. Only worth it for dense graphs or when you need frequent edge lookups.

Traversal is the core operation, and it's always O(V + E): you visit every vertex once and look at every edge once. The two traversal strategies are:

• BFS (breadth-first search): explore layer by layer using a queue. Finds shortest paths in unweighted graphs.
• DFS (depth-first search): explore as deep as possible before backtracking, using recursion or an explicit stack. Natural for cycle detection, topological sort, and connected-component problems.

Because graphs allow cycles, every traversal must track a visited set: without it, you'll revisit nodes indefinitely and infinite-loop on any cyclic input.

// Adjacency list representation
const graph = {
  A: ['B', 'C'],
  B: ['A', 'D'],
  C: ['A', 'D'],
  D: ['B', 'C'],
};

// DFS: recursive, O(V + E) time, O(V) space for the visited set + call stack
function dfs(graph, start, visited = new Set()) {
  if (visited.has(start)) return [];
  visited.add(start);

  const order = [start];
  for (const neighbor of graph[start] ?? []) {
    order.push(...dfs(graph, neighbor, visited));
  }
  return order;
}

// BFS: iterative with a queue, finds shortest path in an unweighted graph
function bfsShortestPath(graph, start, target) {
  const visited = new Set([start]);
  const queue = [[start, [start]]]; // [node, pathSoFar]
  let head = 0;

  while (head < queue.length) {
    const [node, path] = queue[head++];
    if (node === target) return path;

    for (const neighbor of graph[node] ?? []) {
      if (!visited.has(neighbor)) {
        visited.add(neighbor);
        queue.push([neighbor, [...path, neighbor]]);
      }
    }
  }

  return null; // no path exists
}

Common Mistakes

• Forgetting the visited set: the single most common graph bug; without it, cyclic graphs cause infinite recursion or infinite loops.
• Marking visited too late: in BFS, marking a node visited at dequeue time instead of enqueue time lets the same node get added to the queue multiple times before it's ever processed.
• Using DFS when BFS is required (or vice versa): DFS does not guarantee the shortest path in an unweighted graph; only BFS does, because it explores strictly by distance layer.
• Ignoring directionality: treating a directed graph's adjacency list as if edges were bidirectional, which silently produces wrong reachability or cycle-detection results.
• Stack overflow on deep recursive DFS: for graphs with long chains, recursive DFS can blow the call stack; an iterative DFS with an explicit stack avoids this.

Pattern Summary

Reach for a graph model whenever relationships between entities matter more than any single hierarchy: shortest-path, connected-components, cycle-detection, and topological-sort (dependency-ordering) problems are all graph problems in disguise, even when the prompt doesn't say the word "graph." The edge it gives you in interviews is recognizing that a grid, a course-prerequisite list, or a social network is really just nodes and edges, at which point BFS/DFS with a visited set solves most of the work.