05 — Graphs

The email asks for the three representations with their pros and cons, by name. That is the part most candidates have never articulated, and it takes twenty seconds to answer well.

Prereqs: 01, 04 · Reading: 7 min · Cards: 11 · Code: code/graphs.py, code/unionfind.py

The map

Half the difficulty in graph problems is noticing that you have one. A grid is a graph where each cell is a vertex and its neighbours are edges. A set of prerequisites is a directed graph. A word ladder is a graph whose edges you generate rather than store. Once you say "this is a graph", the rest is choosing a representation and a traversal, and there are only three of each.

The choice of traversal is almost mechanical: BFS for fewest steps on unweighted edges, DFS for connectivity, cycles and anything recursive. The choice of representation depends on density. And two specialised tools — topological sort and union-find — cover the problems about ordering and grouping respectively.

What decides your score here

The three representations, defended rather than listed. Adjacency list by default because real graphs are sparse; matrix when the graph is dense or edge lookup dominates; objects and pointers when the nodes are real entities you are mutating. Twenty seconds, with the reason attached to each.

Marking visited at the right moment. Marking on dequeue rather than enqueue is a real bug that lets the same node enter the queue many times. It is a small thing that reads as carelessness.

Naming the right cycle-detection tool. Union-find for undirected, three-colour DFS or Kahn for directed. Using union-find on a directed graph is a wrong answer that sounds confident.

The three representations

Adjacency list stores, for each vertex, the vertices it connects to. Memory is O(V + E), finding neighbours is proportional to the degree, and checking a specific edge means scanning that list. It is the default because real graphs — social networks, maps, dependency graphs — are sparse, and with it BFS, DFS and Dijkstra are all O(V + E).

Adjacency matrix stores a V×V grid of booleans or weights. Checking whether an edge exists is constant, which is its whole advantage, but iterating one vertex's neighbours costs O(V) because you scan a whole row, and memory is O(V²). A million sparse vertices would need 10¹² cells, so it is viable only when the graph is dense or V is small. It also unlocks matrix algebra: Floyd-Warshall and path counting by matrix powers.

Objects and pointers — nodes holding references to other nodes — is what you use when the graph is your domain model: a syntax tree, the DOM, a linked structure you are mutating. The cost is that there is no global index, so "visit every vertex" requires a traversal rather than a loop.

Say the whole thing as one answer: "Adjacency list by default — real graphs are sparse and it gives O(V plus E) traversals. Matrix when the graph is dense or when I need constant-time edge lookups. Objects and pointers when the nodes are real entities I'm mutating, like a DOM tree."

BFS and DFS

BFS uses a queue and explores level by level, which is why it finds the fewest edges on an unweighted graph. DFS uses a stack or recursion and is what you want for connectivity, cycle detection, topological sort, and anything with backtracking. Both are O(V + E).

The space differs, and that is the trade-off the email asks about. BFS costs O(maximum width), DFS costs O(maximum depth). On a wide, shallow graph BFS explodes in memory while DFS is cheap; on a narrow, deep one it reverses, and in Python recursive DFS also hits the recursion limit. In a large maze with a shallow solution, BFS finds it quickly while DFS can wander a long way first.

Two implementation details. Mark visited when you enqueue, not when you dequeue — otherwise the same node enters the queue several times before it is first processed and the cost blows up. And multi-source BFS is not a different algorithm: you seed the queue with every source at once and the wavefront expands from all of them in lockstep. That is the whole solution to Rotting Oranges, and people overcomplicate it by running one search per source.

Topological sort

Only exists on a directed acyclic graph. It orders the vertices so every edge points forwards.

Kahn's algorithm is the one to write: compute every vertex's in-degree, enqueue the zeros, and repeatedly dequeue a vertex, output it, and decrement its neighbours, enqueuing any that reach zero. The dequeue order is the topological order. And if the output is shorter than the vertex count, some vertex never reached in-degree zero — which means a cycle. That is how you detect a cycle in a directed graph, and it comes free with the sort.

The DFS alternative is reversed post-order, which is shorter to write but needs three colours to detect cycles: white for unseen, grey for on the current stack, black for finished. An edge into a grey node is a cycle. Both are O(V + E); pick whichever you can write cleanly under pressure.

Union-find

Disjoint sets with two operations, find and union. With path compression and union by rank the amortised cost is O(α(n)) — inverse Ackermann, which is below five for any n in the observable universe. Treat it as constant, but say the real name: that precision is worth a point, and claiming exactly O(1) is the kind of small overclaim interviewers notice.

Use it for connected components, cycle detection in undirected graphs, Kruskal's MST, and dynamic grouping. It is no use for directed graphs, shortest paths, or undoing a union — it has no notion of direction and no history.

Grids are graphs

Almost every matrix problem is a traversal in disguise. Each cell is a vertex with up to four neighbours; the bounds check is the edge condition.

DIRS = ((0,1), (0,-1), (1,0), (-1,0))
def neighbours(r, c, grid):
    for dr, dc in DIRS:
        nr, nc = r + dr, c + dc
        if 0 <= nr < len(grid) and 0 <= nc < len(grid[0]):
            yield nr, nc

That bounds check is the most common off-by-one in grid problems. And say the reframing out loud — "I'll treat each cell as a vertex with four neighbours, so this is a graph traversal" — because it tells the interviewer you recognised the shape rather than pattern-matched the syntax.

Say it

Cover the answers. Out loud, in English.

Now do this

Four problems, in order.

1. Number of Islands — 20 min. Say the grid-as- graph reframing out loud before writing.
2. Rotting Oranges — 20 min. Multi-source BFS.
3. Course Schedule II — 25 min. Kahn, and say how the cycle detection falls out of it.
4. Number of Provinces — 20 min. Union-find with path compression, from scratch.

Stop when you can give the three-representations answer in twenty seconds and write Kahn's algorithm without reference.