4.19.1 — Graphs: Representation, BFS & DFS

A tree says every node has exactly one parent and there are no cycles. Drop both rules and you have a graph: a set of vertices (nodes) joined by edges, with no restriction on how they connect. A vertex can have twenty neighbours, an edge can loop back on itself, and you can walk in a circle forever.

That freedom is what makes graphs the right model for almost everything real. Road networks, social follows, package dependencies, web links, task prerequisites, state machines, database foreign keys, container orchestration, and the call graph of your own program are all graphs. So a very large share of hard problems reduce to "this is a graph, and the question is one of about six standard graph questions".

1. The vocabulary, all of it, once

• Directed — edges have a direction. A follows B does not mean B follows A. Drawn with arrows.
• Undirected — edges go both ways. Friendship, physical roads.
• Weighted — each edge carries a number: distance, cost, latency, capacity.
• Degree — how many edges touch a vertex. In a directed graph, in-degree counts arrows arriving and out-degree counts arrows leaving.
• Path — a sequence of vertices each joined to the next.
• Cycle — a path that returns to where it started.
• DAG — a directed acyclic graph: directed, with no cycles. Enormously important, because "no cycles" means there is a valid order to process things in, which section 4.19.2 turns into topological sort.
• Connected — in an undirected graph, every vertex is reachable from every other. A connected component is a maximal group that is internally connected.
• Strongly connected — in a directed graph, every vertex can reach every other following the arrows. Much stronger, and much rarer.
• Dense versus sparse — a graph with V vertices can have at most about V^2 edges. If E is close to V^2 it is dense; if E is closer to V it is sparse. Nearly every real graph is sparse: your social network has millions of users and each follows a few hundred, not a few million.

Throughout, V is the number of vertices and E the number of edges, and every complexity below is written in both.

2. Two representations, and how to choose

Adjacency matrix — a V \times V grid where m[i][j] is 1 (or the weight) if there is an edge from i to j.

const m = [
  [0, 1, 1, 0],   // vertex 0 connects to 1 and 2
  [1, 0, 0, 1],
  [1, 0, 0, 1],
  [0, 1, 1, 0],
];
const connected = m[0][2] === 1;   // O(1) — instant answer

Adjacency list — for each vertex, the list of its neighbours.

const adj = new Map<number, number[]>([
  [0, [1, 2]],
  [1, [0, 3]],
  [2, [0, 3]],
  [3, [1, 2]],
]);
const neighbours = adj.get(0)!;    // O(1) to get the list, O(degree) to walk it

	Matrix	List
Space	O(V^2)	O(V + E)
Is there an edge i→j?	O(1)	O(\text{degree})
Walk all neighbours of i	O(V)	O(\text{degree})
Add an edge	O(1)	O(1)
Best for	dense graphs, edge lookups	sparse graphs, traversal

The list wins almost always, and the reason is arithmetic. A social graph with a million users averaging 200 friends has E = 2 \times 10^8 edges — the list stores 200 million entries. The matrix stores 10^{12} cells, of which 99.98% are zero. That is a terabyte of nothing.

The other reason is the second row of that table. Every traversal algorithm's inner loop is "visit all neighbours of the current vertex". The list does that in time proportional to the actual number of neighbours; the matrix scans all V cells whether or not they are edges. That difference alone turns BFS from O(V + E) into O(V^2).

Use a matrix when the graph is genuinely dense, when V is small and fixed (a chessboard, a 20-city tour), or when the algorithm is defined in terms of the matrix — Floyd-Warshall in 4.19.3 is.

A grid is a graph in disguise, and this is the most useful realisation in the whole chapter. A great many problems are stated as "a 2-D grid of cells" — islands, rotting oranges, maze paths, flood fill. Every cell is a vertex, and its neighbours are the up/down/left/right cells that are in bounds. You never build an adjacency list; you generate neighbours on the fly:

const DIRS = [[-1, 0], [1, 0], [0, -1], [0, 1]];              // (1)

function* neighbours(r: number, c: number, grid: string[][]) {  // (2)
  for (const [dr, dc] of DIRS) {
    const nr = r + dr, nc = c + dc;
    if (nr >= 0 && nr < grid.length && nc >= 0 && nc < grid[0].length) {   // (3)
      yield [nr, nc] as const;
    }
  }
}

1. The four up, down, left and right moves. Add the four diagonals if the problem says 8-directional — and read the problem carefully, because it usually says which.
2. A generator (Chapter 3.6.6), so callers can just write for (const [nr, nc] of neighbours(r, c, grid)).
3. The bounds check is the entire "does this edge exist" question for a grid. Getting it wrong — checking only one dimension, or checking after indexing — is the most common bug in grid problems.

3. Breadth-first search: a queue, and the shortest path in edges

BFS visits everything at distance 1, then everything at distance 2, and so on. It is level-order traversal from Chapter 4.13.1, generalised to a structure that can have cycles.

function bfs(start: number, adj: Map<number, number[]>): Map<number, number> {
  const dist = new Map<number, number>([[start, 0]]);   // (1)  doubles as the visited set
  const queue: number[] = [start];
  let head = 0;                                          // (2)

  while (head < queue.length) {
    const node = queue[head++];                          // (3)
    for (const next of adj.get(node) ?? []) {
      if (dist.has(next)) continue;                      // (4)
      dist.set(next, dist.get(node)! + 1);               // (5)
      queue.push(next);
    }
  }
  return dist;
}

1. One map serves two purposes: it records the distance and it is the visited set. Keeping them separate is a common source of bugs where a node gets queued twice.
2. and 3. A head index instead of queue.shift(). Chapter 4.7 explained why: shift is O(n) and turns BFS into O(V^2). This is a real production mistake, not a style preference.
3. The visited check is what makes graphs different from trees. A tree traversal needs none, because there is exactly one path to each node. A graph has cycles, and without this line BFS runs forever.
4. Distance is the parent's distance plus one.

Mark visited when you enqueue, not when you dequeue. If you mark on dequeue, a node with three neighbours pointing at it gets pushed three times before any of them is processed, and the queue fills with duplicates. On a dense graph that is an exponential blow-up. This is the single most common BFS bug.

Complexity is O(V + E): each vertex enters the queue at most once, and each edge is examined at most once (twice in an undirected graph, once from each end). Space is O(V) for the visited set plus the queue, whose peak size is the widest level.

Why BFS gives shortest paths. Because it processes vertices in non-decreasing order of distance. When it first reaches a vertex, no shorter route can exist — any shorter route would have gone through a vertex at a smaller distance, which was already fully processed. The proof is that simple, and it carries one crucial condition: every edge must cost the same. BFS counts edges, not weights. The moment edges have different costs, BFS gives the path with the fewest hops, which may be far more expensive, and you need Dijkstra (4.19.3).

Multi-source BFS is a small trick that solves a whole family of problems. Instead of one starting vertex, put all the sources in the queue at distance 0. The search expands from all of them simultaneously, and every vertex gets its distance to the nearest source. "How many minutes until every orange rots, given several rotten ones" and "distance from each cell to the nearest gate" are both this, and both look much harder if you do not know it.

4. Depth-first search: go deep, then back up

DFS follows one path as far as it goes, then backtracks and tries the next branch.

function dfsIterative(start: number, adj: Map<number, number[]>): Set<number> {
  const visited = new Set<number>();
  const stack = [start];                                 // (1)
  while (stack.length > 0) {
    const node = stack.pop()!;
    if (visited.has(node)) continue;                     // (2)
    visited.add(node);
    for (const next of adj.get(node) ?? []) {
      if (!visited.has(next)) stack.push(next);
    }
  }
  return visited;
}

1. A stack instead of a queue is the only structural difference from BFS. That one substitution changes the visiting order completely, which is a good demonstration of how much a data structure choice can mean.
2. Here we check visited on pop, not on push, because a vertex can legitimately be pushed several times before being processed and we want the check at the point of work.

The recursive form is usually cleaner and is what you write in an interview:

function dfs(node: number, adj: Map<number, number[]>, visited = new Set<number>()): void {
  if (visited.has(node)) return;
  visited.add(node);                                     // (1)  pre-order: act on the way down
  for (const next of adj.get(node) ?? []) dfs(next, adj, visited);
  // (2)  post-order position: act here on the way back up
}

1. Work done here happens on the way down — this is pre-order.
2. Work done after the loop happens after every descendant is finished — this is post-order, and it is where topological sort and cycle detection live (4.19.2).

O(V + E) time, and O(V) space for the stack — but note that the recursive version's space is the call stack, so a graph with a path 100,000 vertices long overflows it. On large graphs, use the iterative form.

5. Choosing between them

Question	Use	Why
Shortest path, unweighted	BFS	processes in distance order
Does a path exist?	either	both explore everything reachable
All connected components	either	loop over unvisited vertices, traverse each
Cycle detection	DFS	needs the recursion-stack idea (4.19.2)
Topological sort	DFS	post-order gives reverse topological order
Explore level by level	BFS	that is its definition
Backtracking / all paths	DFS	it is backtracking (Chapter 4.12)
Very deep graph, limited stack	BFS	or iterative DFS
Very wide graph, limited memory	DFS	BFS's queue holds a whole level

The memory trade in the last two rows is the one to remember: BFS's memory is the width of the graph, DFS's is the depth. On a binary tree of a million nodes, BFS's last level holds 500,000 nodes and DFS's stack holds 20 frames. On a linked-list-shaped graph, BFS holds one node and DFS holds a million.

6. Connected components, and the shape of most grid problems

Counting connected components is the template that a surprising number of problems reduce to:

function countIslands(grid: string[][]): number {
  const rows = grid.length, cols = grid[0].length;
  const seen = new Set<string>();                        // (1)
  let count = 0;

  const flood = (r: number, c: number): void => {        // (2)
    const key = `${r},${c}`;
    if (r < 0 || r >= rows || c < 0 || c >= cols) return;   // (3)
    if (grid[r][c] !== '1' || seen.has(key)) return;        // (4)
    seen.add(key);
    flood(r + 1, c); flood(r - 1, c); flood(r, c + 1); flood(r, c - 1);   // (5)
  };

  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      if (grid[r][c] === '1' && !seen.has(`${r},${c}`)) { count++; flood(r, c); }   // (6)
    }
  }
  return count;
}

1. A string key because JavaScript's Set compares arrays by identity, so [1,2] never equals another [1,2]. Encoding as r * cols + c into a numeric set is faster and worth doing on large grids.
2. A DFS written as a closure so it captures grid and seen without threading them through every call.
3. Out of bounds — this is the "edge does not exist" case for a grid.
4. Water, or already counted. Combining the two conditions here means the caller never has to check anything.
5. The four neighbours.
6. The outer double loop is what counts components. Every time we find land that no previous flood reached, we have found a new island, so we increment and then flood the entire thing so it is never counted again.

O(rows \times cols): every cell is visited a constant number of times.

Recognise this shape and a long list of problems collapses into it: number of islands, max area of island, surrounded regions, flood fill, counting provinces, and "number of distinct groups of connected accounts". Chapter 4.20 works through all of them, and every one is either this template or this template with something counted during the flood.

The one warning: recursive flood fill on a 1000×1000 grid that is entirely land recurses a million deep and overflows the stack. Convert to the iterative stack version, or use the union-find structure from 4.19.2, which handles this shape without any recursion at all.

What the interviewer will push on

"Adjacency list or matrix?" The answer must contain the density argument with a number. A million users at 200 friends each is 200 million list entries versus 10^{12} matrix cells. Also mention the second reason — every traversal's inner loop is "walk the neighbours", which the list does in O(\text{degree}) and the matrix in O(V).

"Why does BFS find the shortest path but DFS does not?" BFS processes vertices in non-decreasing distance order, so the first time it reaches a vertex is via a shortest route. DFS commits to one branch and may reach a vertex the long way round first. Then add the condition that makes the claim true: all edges must have equal weight.

"Where do you mark a node as visited in BFS?" On enqueue. Marking on dequeue lets the same node be queued many times before any of them is processed. This is asked because it is the bug everyone writes once.

"Your BFS uses queue.shift(). Any concern?" O(n) per call, making BFS O(V^2). Use a head index or a real deque.

"BFS or DFS for a graph with a million vertices?" It depends on the shape, and saying so is the answer. BFS's memory is the widest level; DFS's is the longest path. Then note that recursive DFS risks a stack overflow where iterative DFS does not, because the heap is far larger than the call stack.

One thing to volunteer: point out that a grid is a graph whose adjacency is computed rather than stored, so no graph is ever built. Interviewers hear a lot of candidates try to construct an adjacency list from a grid, which wastes time and memory for no gain.

Recall

• A graph is vertices plus edges with no restrictions; V is vertex count and E edge count, and nearly every real graph is sparse (E \ll V^2).
• An adjacency list costs O(V+E) space and walks neighbours in O(\text{degree}); a matrix costs O(V^2) and walks in O(V). Use the list unless the graph is genuinely dense.
• A grid is a graph whose neighbours are computed from the four direction offsets plus a bounds check — never build an adjacency list for one.
• BFS uses a queue and gives the shortest path when all edges cost the same; mark visited on enqueue, and never use array.shift() as the dequeue.
• DFS uses a stack (or recursion); its post-order position is where topological sort and cycle detection live.
• BFS's memory is the graph's width, DFS's is its depth — that is how you choose on a huge graph.
• Multi-source BFS seeds the queue with every source at distance 0 and gives each vertex its distance to the nearest one.

Self-test: Why must every edge have equal weight for BFS to give shortest paths? · What goes wrong if you mark visited on dequeue instead of enqueue? · Why does an adjacency matrix make BFS O(V^2)? · When is DFS the wrong choice on a large graph, and when is BFS? · Describe the outer loop that turns a flood fill into a component count.

Next: 4.19.2 uses DFS's post-order position to answer the two questions a dependency graph asks — is there a cycle, and in what order can I process this — and introduces union-find, which answers connectivity almost without any traversal at all.