Chapter 12 — Graphs & BFS/DFS

Connect Backward

Every data structure you've seen so far is a special case of a graph:

• Array — nodes in a line, each connected to the next
• Linked list — same, but the connections are pointers instead of indices
• Tree — nodes connected with exactly one path between any two nodes, no cycles
• Binary search tree — tree with ordering constraint

A graph removes the tree's restrictions: nodes can have any number of connections, in any direction, and there can be cycles (you can get back to where you started). This makes graphs the most general structure — and the most powerful.

Chapter 10 taught DFS on trees. Tree DFS never needed a visited set because trees have no cycles — you can't accidentally revisit a node. Graph DFS requires a visited set. That's the critical addition.

Chapter 11 (Backtracking) was DFS on an implicit decision tree. Graph DFS is DFS on an explicit stored graph. Same traversal logic, different data source.

1. The Physical Reality

A graph is a collection of nodes (also called vertices) and edges (connections between nodes).

Physical analogy: Cities and roads. Cities are nodes. Roads are edges. A road can be one-way (directed edge) or two-way (undirected edge). A road can have a toll (weighted edge) or be free (unweighted).

Real example — Facebook social graph:

• Nodes: user profiles
• Edges: friend connections (undirected — if A is B's friend, B is A's friend)
• 3 billion nodes, ~500 billion edges
• "Find all friends of friends" = BFS to depth 2

Real example — Web graph:

• Nodes: web pages
• Edges: hyperlinks (directed — page A links to page B doesn't mean B links to A)
• Google's core insight (PageRank) is that important pages have many inbound edges

2. Graph Vocabulary

3. Representing a Graph in Code

Adjacency List (preferred)

For each node, store the list of its neighbors.

// Undirected graph: 0-1, 0-2, 1-2, 1-3
const graph = {
  0: [1, 2],
  1: [0, 2, 3],
  2: [0, 1],
  3: [1]
};

// Or as array of arrays (when nodes are 0..n-1)
const graph = [
  [1, 2],    // node 0's neighbors
  [0, 2, 3], // node 1's neighbors
  [0, 1],    // node 2's neighbors
  [1]        // node 3's neighbors
];

Space: O(V + E) — V nodes, E total edges across all adjacency lists.
Lookup "is X neighbor of Y"? O(degree of Y) — scan Y's list.
Iterate all edges: O(E).

Adjacency Matrix

A V×V grid where matrix[i][j] = 1 means there's an edge from i to j.

// Same graph as above (4 nodes)
const matrix = [
  [0, 1, 1, 0],
  [1, 0, 1, 1],
  [1, 1, 0, 0],
  [0, 1, 0, 0]
];

Space: O(V²) — even if the graph has few edges.
Lookup "is X neighbor of Y"? O(1).
Iterate all edges: O(V²) — must scan entire matrix.

When to use which? Adjacency list for sparse graphs (few edges relative to V²), which is most real-world graphs. Adjacency matrix for dense graphs or when O(1) edge lookup is critical.

Building a Graph from Edge List

Interviews often give you a list of edges: [[0,1],[0,2],[1,3]]. Build the adjacency list:

function buildGraph(n, edges) {
  const graph = Array.from({ length: n }, () => []);
  for (const [u, v] of edges) {
    graph[u].push(v);
    graph[v].push(u);  // omit this line for directed graph
  }
  return graph;
}

4. BFS — Breadth-First Search

Physical reality: You're exploring a maze. Instead of rushing down one corridor (DFS), you advance all corridors simultaneously, one step at a time. After k steps, you've visited all nodes reachable in exactly k edges.

Data structure needed: Queue (FIFO). Each level of the BFS uses the queue to hold the frontier — all nodes at the current distance.

Core property: BFS from a source node visits all nodes at distance 1, then all at distance 2, etc. This gives the shortest path (in terms of edge count) in an unweighted graph.

function bfs(graph, start) {
  const visited = new Set([start]);
  const queue = [start];
  
  while (queue.length > 0) {
    const node = queue.shift();  // dequeue front
    
    // process node
    console.log(node);
    
    for (const neighbor of graph[node]) {
      if (!visited.has(neighbor)) {
        visited.add(neighbor);
        queue.push(neighbor);  // enqueue
      }
    }
  }
}

Why mark visited when enqueueing, not when dequeueing? If you wait until dequeue, the same node can be enqueued multiple times (by different neighbors), causing it to be processed multiple times and potentially causing cycles. Mark visited at enqueue time to prevent duplicates in the queue.

BFS with level tracking (for shortest path):

function bfsShortestPath(graph, start, end) {
  if (start === end) return 0;
  
  const visited = new Set([start]);
  const queue = [start];
  let distance = 0;
  
  while (queue.length > 0) {
    const levelSize = queue.length;  // process one full level
    distance++;
    
    for (let i = 0; i < levelSize; i++) {
      const node = queue.shift();
      
      for (const neighbor of graph[node]) {
        if (neighbor === end) return distance;
        if (!visited.has(neighbor)) {
          visited.add(neighbor);
          queue.push(neighbor);
        }
      }
    }
  }
  
  return -1;  // unreachable
}

Time complexity: O(V + E) — every vertex enqueued at most once, every edge examined at most twice (once from each endpoint in undirected graphs).

Space complexity: O(V) — the queue holds at most one full level, which can be O(V) in the worst case.

5. DFS — Depth-First Search

Physical reality: Explore a maze by always taking the first available path until you hit a dead end, then backtrack and try the next path.

Two implementations:

Recursive DFS

function dfs(graph, node, visited) {
  visited.add(node);
  console.log(node);
  
  for (const neighbor of graph[node]) {
    if (!visited.has(neighbor)) {
      dfs(graph, neighbor, visited);
    }
  }
}

// Call:
const visited = new Set();
dfs(graph, startNode, visited);

Iterative DFS (with explicit stack)

function dfsIterative(graph, start) {
  const visited = new Set();
  const stack = [start];
  
  while (stack.length > 0) {
    const node = stack.pop();  // pop from top
    
    if (visited.has(node)) continue;
    visited.add(node);
    console.log(node);
    
    for (const neighbor of graph[node]) {
      if (!visited.has(neighbor)) {
        stack.push(neighbor);
      }
    }
  }
}

Note: Iterative DFS marks visited at pop time (not push), unlike BFS. This is because a stack can have duplicate entries — we want to process a node on first pop and skip it on subsequent pops. Both implementations produce a valid DFS traversal but may visit neighbors in different orders.

Time complexity: O(V + E) — same as BFS.
Space complexity: O(V) — call stack (recursive) or explicit stack.

BFS vs DFS — When to use which?

Key mental model: BFS is like dropping a stone in water — waves expand outward uniformly. DFS is like following a thread through a maze — go as deep as possible before turning back.

6. Cycle Detection

In Undirected Graphs

During DFS, if you visit a neighbor that is already visited AND is not the parent of the current node, there's a cycle.

function hasCycleUndirected(graph, node, visited, parent) {
  visited.add(node);
  
  for (const neighbor of graph[node]) {
    if (!visited.has(neighbor)) {
      if (hasCycleUndirected(graph, neighbor, visited, node)) return true;
    } else if (neighbor !== parent) {
      return true;  // visited neighbor that isn't our parent = cycle
    }
  }
  return false;
}

Why exclude parent? In an undirected graph, the edge A-B appears in both graph[A] (neighbor B) and graph[B] (neighbor A). When DFS goes A→B and then checks B's neighbors, it sees A again. But that's just the same edge — not a cycle. We exclude parent (A) to avoid this false positive.

In Directed Graphs

Undirected cycle detection doesn't work for directed graphs. In a directed graph, A→B and A→C→B is not a cycle (B is visited but not via a back-edge to A).

For directed graphs, we need to detect back edges — edges that point to an ancestor in the current DFS path. We use a recursionStack (nodes in the current path, not just visited):

function hasCycleDirected(graph, node, visited, recStack) {
  visited.add(node);
  recStack.add(node);
  
  for (const neighbor of graph[node]) {
    if (!visited.has(neighbor)) {
      if (hasCycleDirected(graph, neighbor, visited, recStack)) return true;
    } else if (recStack.has(neighbor)) {
      return true;  // back edge to current path = cycle
    }
  }
  
  recStack.delete(node);  // leaving this node's subtree
  return false;
}

visited tracks all nodes ever seen. recStack tracks only nodes in the current DFS path. A node in recStack that we encounter again = we've found a cycle.

7. Topological Sort

A topological sort of a DAG (Directed Acyclic Graph) is a linear ordering of nodes such that for every edge A→B, A comes before B.

Use case: Task scheduling. If task B depends on task A, A must appear before B. npm package installation order. Course prerequisites.

Only exists if the graph has no cycles. If there's a cycle (A depends on B, B depends on A), no valid ordering exists.

Kahn's Algorithm (BFS-based)

Key insight: A node with in-degree 0 has no prerequisites — it can be processed first. After processing it, reduce the in-degree of its neighbors. Any neighbor whose in-degree drops to 0 can now be processed.

function topoSortKahn(n, edges) {
  const graph = Array.from({ length: n }, () => []);
  const inDegree = new Array(n).fill(0);
  
  for (const [u, v] of edges) {
    graph[u].push(v);
    inDegree[v]++;
  }
  
  const queue = [];
  for (let i = 0; i < n; i++) {
    if (inDegree[i] === 0) queue.push(i);
  }
  
  const result = [];
  while (queue.length > 0) {
    const node = queue.shift();
    result.push(node);
    
    for (const neighbor of graph[node]) {
      inDegree[neighbor]--;
      if (inDegree[neighbor] === 0) queue.push(neighbor);
    }
  }
  
  // If result.length < n, there's a cycle (some nodes never reached in-degree 0)
  return result.length === n ? result : [];
}

Full dry run — 4 courses with prerequisites:

n=4, edges=[[1,0],[2,0],[3,1],[3,2]]
Meaning: 0 requires 1, 0 requires 2, 1 requires 3, 2 requires 3

Build graph:
  graph[1]=[0], graph[2]=[0], graph[3]=[1,2]
  inDegree: [2, 1, 1, 0]
   (node 0 has 2 deps, node 1 has 1, node 2 has 1, node 3 has 0)

Initial queue (in-degree 0): [3]

Step 1: dequeue 3, push to result=[3]
  neighbors: 1, 2
  inDegree[1]-- = 0 → enqueue 1
  inDegree[2]-- = 0 → enqueue 2
  queue=[1, 2]

Step 2: dequeue 1, result=[3,1]
  neighbors: 0
  inDegree[0]-- = 1
  queue=[2]

Step 3: dequeue 2, result=[3,2,1]
  Wait — wrong order. Let me redo:
  result=[3,1] → dequeue 2
  neighbors: 0
  inDegree[0]-- = 0 → enqueue 0
  queue=[0]

Step 3 (corrected): dequeue 2, result=[3,1,2]
  inDegree[0]-- = 0 → enqueue 0
  queue=[0]

Step 4: dequeue 0, result=[3,1,2,0]
  no neighbors
  queue=[]

result.length=4=n → valid. Return [3,1,2,0]

Order: take course 3 first, then 1, then 2, then 0. ✓

Cycle detection with Kahn's: If the result array has fewer than n nodes, some nodes were never added to the queue (their in-degree never reached 0), meaning they're part of a cycle.

DFS-based Topological Sort

Post-order DFS, then reverse:

function topoSortDFS(n, edges) {
  const graph = Array.from({ length: n }, () => []);
  for (const [u, v] of edges) graph[u].push(v);
  
  const visited = new Set();
  const result = [];
  
  function dfs(node) {
    visited.add(node);
    for (const neighbor of graph[node]) {
      if (!visited.has(neighbor)) dfs(neighbor);
    }
    result.push(node);  // push AFTER all dependencies are processed
  }
  
  for (let i = 0; i < n; i++) {
    if (!visited.has(i)) dfs(i);
  }
  
  return result.reverse();
}

A node is pushed after all nodes it points to have been processed. Reversing gives the topological order.

8. Connected Components

Count disconnected subgraphs:

function countComponents(n, edges) {
  const graph = Array.from({ length: n }, () => []);
  for (const [u, v] of edges) {
    graph[u].push(v);
    graph[v].push(u);
  }
  
  const visited = new Set();
  let components = 0;
  
  function dfs(node) {
    visited.add(node);
    for (const neighbor of graph[node]) {
      if (!visited.has(neighbor)) dfs(neighbor);
    }
  }
  
  for (let i = 0; i < n; i++) {
    if (!visited.has(i)) {
      dfs(i);      // explore entire component
      components++;
    }
  }
  
  return components;
}

Mental model: Imagine dropping a bucket of water on each unvisited node. The water floods through all edges. Count how many times you pour water before the whole graph is wet. Each pour = one component.

9. Grid as Graph

Many interview problems give you a 2D grid. Every cell is a node. Adjacent cells (up/down/left/right) are edges. No explicit graph is built — neighbors are computed from (r, c).

const dirs = [[1,0],[-1,0],[0,1],[0,-1]];

function bfsGrid(grid, startR, startC) {
  const rows = grid.length, cols = grid[0].length;
  const visited = Array.from({ length: rows }, () => new Array(cols).fill(false));
  
  visited[startR][startC] = true;
  const queue = [[startR, startC]];
  
  while (queue.length > 0) {
    const [r, c] = queue.shift();
    
    for (const [dr, dc] of dirs) {
      const nr = r + dr, nc = c + dc;
      if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && !visited[nr][nc]) {
        visited[nr][nc] = true;
        queue.push([nr, nc]);
      }
    }
  }
}

10. Union-Find (Disjoint Set Union)

An alternative to BFS/DFS for connectivity problems. Tracks which nodes are in the same component using an array.

Operations:

• find(x): which component does x belong to? (returns representative)
• union(x, y): merge x's and y's components

class UnionFind {
  constructor(n) {
    this.parent = Array.from({ length: n }, (_, i) => i);
    this.rank = new Array(n).fill(0);
    this.components = n;
  }
  
  find(x) {
    if (this.parent[x] !== x) {
      this.parent[x] = this.find(this.parent[x]);  // path compression
    }
    return this.parent[x];
  }
  
  union(x, y) {
    const px = this.find(x), py = this.find(y);
    if (px === py) return false;  // already same component
    
    // union by rank: attach smaller tree under larger
    if (this.rank[px] < this.rank[py]) {
      this.parent[px] = py;
    } else if (this.rank[px] > this.rank[py]) {
      this.parent[py] = px;
    } else {
      this.parent[py] = px;
      this.rank[px]++;
    }
    this.components--;
    return true;
  }
}

Path compression (this.parent[x] = this.find(this.parent[x])) flattens the tree — after finding the root, every node on the path points directly to the root. This makes future find calls faster.

With both path compression and union by rank, find and union are effectively O(1) amortized — technically O(α(n)) where α is the inverse Ackermann function, which is ≤ 4 for any practical n.

When to use Union-Find over BFS/DFS:

• Dynamic connectivity — edges are added one at a time, and you need to answer "are X and Y connected?" after each addition
• Redundant connections — detect the edge that creates a cycle
• Kruskal's MST algorithm

11. Shortest Path Algorithms

For unweighted graphs: BFS gives shortest path in O(V + E).

For weighted graphs with non-negative weights: Dijkstra's algorithm.

function dijkstra(graph, start) {
  // graph[u] = [[v, weight], ...]
  const dist = new Array(graph.length).fill(Infinity);
  dist[start] = 0;
  
  // Min-heap: [distance, node]
  // JavaScript doesn't have a built-in min-heap.
  // Interview: use sorted array (slower) or implement a heap.
  const minHeap = [[0, start]];
  
  while (minHeap.length > 0) {
    minHeap.sort((a, b) => a[0] - b[0]);  // O(E log E) with array sort
    const [d, u] = minHeap.shift();
    
    if (d > dist[u]) continue;  // stale entry
    
    for (const [v, w] of graph[u]) {
      if (dist[u] + w < dist[v]) {
        dist[v] = dist[u] + w;
        minHeap.push([dist[v], v]);
      }
    }
  }
  
  return dist;
}

The key idea: Always process the node with the smallest known distance next (greedy). When we process a node, its distance is finalized — no shorter path can be found later (because all weights are non-negative).

With a proper binary min-heap: O((V + E) log V).

For negative weights: Bellman-Ford, which relaxes all edges V-1 times: O(V × E). Not typically asked at interviews but worth knowing exists.

12. Mental Model: When to Reach for Graphs

If you see a 2D grid with cells that connect, it's a graph. If you see tasks with prerequisites, it's a DAG. If you see relationships (friends, follows, links), it's a graph.

13. Real Systems That Use Graph Algorithms

Google PageRank: The web is a directed graph. PageRank is an algorithm (iterated random walk) on this graph to assign importance scores. Pages with many inbound edges from important pages rank higher.

npm dependency resolution: package.json dependencies form a DAG. npm install runs topological sort to determine installation order. If there's a circular dependency, npm detects the cycle and errors.

GPS routing (Google Maps): Road network is a weighted directed graph (edges have distances/travel times). Dijkstra's or A* finds shortest path. Real systems use optimizations: precomputed "contraction hierarchies" that reduce query time from seconds to milliseconds.

Social network features: Facebook's "People You May Know" is BFS to depth 2 on the friendship graph. Twitter's timeline ranking involves graph algorithms on the follow graph.

Git internals: Git history is a DAG. Commits are nodes; parent pointers are edges. git merge-base finds the LCA in this DAG. git log --graph does a topological sort of the DAG to display history.

Kubernetes pod scheduling: Pods and their dependencies form a DAG. The scheduler uses topological sort to determine startup order.

V8's garbage collector (mark phase): The object reference graph is traversed with DFS from roots (global scope, call stack). Any reachable object is "marked" as alive. Unreachable objects are collected. This is literally graph DFS inside your Node.js runtime.

Vocabulary Map

Connect Forward

Chapter 12a applies BFS and DFS to 7 high-frequency interview problems. Number of Islands and Course Schedule are top-3 most commonly asked graph problems at FAANG.

Chapter 13 (DP) works on a restricted graph shape: the DAG of overlapping subproblems. Every DP recurrence is a DAG traversal where results are cached. Topological sort of this DAG (which is implicit) determines the computation order. This is why "bottom-up DP" is really topological-order traversal of the subproblem DAG.