Five graph shapes and I've seen them all

A graph is a set of nodes connected by edges. Interviews usually hand you one disguised as something else: a city grid, a dependency chain, a web of friends. The round tests whether you spot the graph and pick the right walk.

Jeff Erickson's Algorithms textbook is free online at jeffe.cs.illinois.edu. The graph chapters are the cleanest interview prep you can read. Erickson walks BFS and DFS as the same algorithm with a different container — queue versus stack — and that reframe does more for a coding-round answer than any template.

Read Erickson's Chapter 5 (Graphs) and Chapter 6 (DFS). Then watch William Fiset's Graph Theory playlist — nine hours, every graph algorithm that shows up in a coding round, worked out on a whiteboard. Open Robert Sedgewick's Princeton Algorithms course materials next to them. Three sources. Free. Enough.

“Graph interviews are not testing graph theory. They test whether you can name the shape in the first minute — then pick the container that matches.”

Most coding-round graph questions reduce to five shapes. Name the shape, pick the tool, explain the state invariant. That is the interview. This post classifies the shapes and hands you off to the engineers who cover each one in depth.

The decision tree

Walk through this before you type anything. Picking the wrong tool is the most common graph-interview failure — more common than an off-by-one inside the traversal itself.

Diagram

Copy source

Rendering diagram...

Green nodes are your first-reach tools on unweighted graphs. Amber means the problem has extra structure — edge weights or ordering constraints — that demands a heavier algorithm.

Shape 1 — Traversal: visit everything once

Number of Islands, Clone Graph, Walls and Gates, every grid flood-fill variant.

The real question is not "BFS or DFS?" Erickson's graph chapter names the three actual questions: what counts as a node, how you generate neighbors, and when you mark a node visited.

The canonical trap is marking visited at the wrong step. Sedgewick's BreadthFirstPaths implementation at Princeton marks visited inside the enqueue step for exactly that reason. Mark it after dequeue and the same node enters the queue multiple times — the complexity blows up and the interviewer reads it as a missed invariant.

PYTHON

Copy

from collections import deque def bfs(start, graph): queue = deque([start]) visited = {start} while queue: node = queue.popleft() for neighbor in graph[node]: if neighbor not in visited: visited.add(neighbor) # mark at enqueue, not dequeue queue.append(neighbor)

The sentence that wins the round: I mark a node visited when I enqueue it, not when I dequeue it, so the same node never enters the queue twice. That sentence is the invariant — the guarantee the algorithm holds at every step. Interviewers are trained to listen for it. Most candidates skip it.

Shape 2 — Shortest path on an unweighted graph

Word Ladder, Open the Lock, Rotting Oranges, Shortest Path in a Binary Matrix.

BFS explores by layer. The first time you reach a node, that is the shortest path length. No heap, no Dijkstra, no priority queue. Equal-weight edges are a hard constraint that admits a lighter algorithm, and naming that constraint is half the answer.

Erickson's single-source shortest paths chapter (08-sssp.pdf) states the invariant plainly: on an unweighted graph, BFS produces a shortest-path tree. NeetCode's Word Ladder walkthrough frames the implicit-graph version of the same result — words as nodes, one-character edits as edges, BFS gives the minimum transformation length.

The sentence that matters: Because every edge has equal cost, BFS gives me the shortest distance without needing Dijkstra. Candidates who lead with a priority queue on an unweighted problem lose points they did not need to lose. If the interviewer wants a weighted follow-up, they will pivot — let them.

Shape 3 — Topological order: prerequisites and dependencies

Course Schedule, Course Schedule II, Alien Dictionary, build orderings, CI dependency graphs.

This shape rarely announces itself as a graph problem. It shows up as course scheduling, build ordering, task execution. The signal: directional dependency. "A must happen before B."

That makes it a DAG-shaped question, and the tool is topological sort. Wikipedia's topological-sorting article has the full history, including Kahn's 1962 in-degree algorithm — the one every production dependency resolver uses today. npm, Cargo, Gradle, Bazel all run Kahn's under the hood.

Kahn's algorithm is the cleanest interview answer because the in-degree invariant is readable from the code:

PYTHON

Copy

from collections import deque def topo_sort(num_courses, prerequisites): graph = {c: [] for c in range(num_courses)} indegree = [0] * num_courses for course, prereq in prerequisites: graph[prereq].append(course) indegree[course] += 1 queue = deque(c for c in range(num_courses) if indegree[c] == 0) order = [] while queue: node = queue.popleft() order.append(node) for neighbor in graph[node]: indegree[neighbor] -= 1 if indegree[neighbor] == 0: queue.append(neighbor) return order if len(order) == num_courses else []

Invariant to say out loud: The queue holds exactly the nodes whose prerequisites are already satisfied.

If the final order is shorter than the total course count, there was a cycle. That is your cycle detection for free. NetworkX's topological_sort in its DAG module is Kahn's algorithm, annotated. Open it after the round and walk the production version.

For the harder follow-up on strongly connected components, Wikipedia on Tarjan's SCC algorithm covers the 1972 single-pass DFS version. If you can name Tarjan's on a staff loop, the interviewer tends to raise the bar — which is the signal you wanted.

Shape 4 — Connectivity: are these nodes in the same group?

Accounts Merge, Redundant Connection, Number of Provinces, dynamic connectivity.

This is where union-find earns its place. Edges arrive as pairs, the question cares about whether two items share a connected component, and re-running BFS from scratch every time a new edge appears is the wrong complexity.

Sedgewick's Princeton course has the canonical union-find lecture — path compression and union-by-rank worked out with measured amortized cost. Google Guava's Graphs library ships production graph implementations in Java; the source is worth a skim if the interviewer pushes on "what does a real codebase use?"

PYTHON

Copy

class UnionFind: def __init__(self, size): self.parent = list(range(size)) self.rank = [1] * size def find(self, x): if self.parent[x] != x: self.parent[x] = self.find(self.parent[x]) # path compression return self.parent[x] def union(self, a, b): ra, rb = self.find(a), self.find(b) if ra == rb: return False if self.rank[ra] < self.rank[rb]: ra, rb = rb, ra self.parent[rb] = ra if self.rank[ra] == self.rank[rb]: self.rank[ra] += 1 return True

The clean one-liner: Union-find gives near-constant-time merges and connectivity checks via path compression and union-by-rank. The time complexity is O(α(n)) per operation — inverse Ackermann, effectively constant. Say that if the interviewer asks. Do not volunteer a proof. Nobody wants a proof in a 45-minute slot.

Shape 5 — "Secretly a graph"

A lot of graph rounds never use the word "graph." They describe grids, flights, transformations, prerequisites, email merges.

Word Ladder is a BFS problem. The words are nodes. A single-character edit is an edge. Rotting Oranges is BFS on a grid. Accounts Merge is union-find on a name graph. The implementation is the template from Shape 1, 2, or 4 — once you see the implicit graph, the code writes itself. NeetCode's Graphs course walks through several of these recognition problems back-to-back, and the pattern lands faster when you do them in sequence.

The habit worth drilling: stop memorizing problem titles, start recognizing the five shapes.

• Traversal — visit every reachable node
• Shortest path — minimum cost to a target
• Ordering — dependencies with direction
• Connectivity — same group or different groups
• Cycle detection — is there a loop in the dependency chain?

Classify in the first minute. The rest of the interview is talking through state.

Common mistakes

Marking visited too late

For BFS, mark at enqueue. Wait until dequeue and the same node enters the queue multiple times — the complexity burns and the interviewer scores it as a missed invariant. Sedgewick's Princeton slides call this out explicitly in the BFS lecture.

Missing the implicit graph

Grids, word transformations, dependency lists are all graphs. The neighbor function is just different. For grids: four cardinal directions. For Word Ladder: every one-character edit. If the implicit graph is invisible, the tool choice will be too.

Reaching for DFS when the prompt asks for minimum distance

Unweighted plus "fewest steps" means BFS. DFS finds a path, not the shortest one. Read the distance language in the prompt before committing to a traversal strategy. If the graph is weighted, the decision tree branches to Dijkstra's algorithm — different shape entirely.

Treating topological sort like generic traversal

If prerequisites matter, say "in-degree" and "cycle" out loud. That signals you understand the problem contract — this is an ordering problem on a DAG, not "explore everything." Interviewers grade on vocabulary as much as code.

Using union-find when you need path details

Union-find tells you whether two nodes are connected. It does not tell you the path between them or the shortest distance. Know what your data structure preserves and what it throws away.

Go deeper — the reading list this post is aggregating

For your next graph round, open these in this order:

• Jeff Erickson, Algorithms — Chapter 5 (Graphs) and Chapter 6 (DFS) — free textbook, University of Illinois. BFS and DFS as one algorithm with a container choice. The single best free graph-algorithm primer online.
• Robert Sedgewick, Princeton Algorithms course — Graphs section — canonical lecture materials. The union-find lecture is a masterclass on amortized analysis.
• William Fiset, Graph Theory playlist — nine hours, every algorithm in scope for coding interviews, walked out on a whiteboard.
• NeetCode (Navdeep Singh), Graphs and Advanced Graphs — problem-by-problem walkthroughs tied to the NeetCode 150.
• Wikipedia — Topological sorting, Tarjan's SCC, Dijkstra's algorithm — reference entries covering the original Kahn 1962, Tarjan 1972, and Dijkstra 1959 papers. Two of those three are under two pages. Read the actual papers once.
• Production open-source — NetworkX is the Python reference implementation; JGraphT is the JVM equivalent. Production code for every algorithm named in this post.

Before the round, open Erickson's chapters 5 and 6 and Sedgewick's graphs page in two tabs. Skim them. That is the prep.

A 2-hour graph drill plan

If you have one serious graph prep block, spend it like this:

1. 25 min — Drill BFS and DFS on one grid problem and one adjacency list problem. Write both from scratch, no templates.
2. 25 min — Do one shortest-path BFS question out loud. Explain why BFS gives the optimal answer on an unweighted graph.
3. 25 min — Do Course Schedule until topological sort feels mechanical. Then do Course Schedule II and return the actual ordering.
4. 20 min — Implement union-find from memory with path compression and union-by-rank. Apply it to Redundant Connection or Accounts Merge.
5. 15 min — Review your visited strategy across all four families. Where do you mark visited? What does your visited set represent? Can you state the invariant for each?
6. 10 min — Take a problem you have not seen before and classify it into one of the five shapes before writing any code. Practice the recognition step.

That covers the surface. You do not need a graduate algorithms course. You need the five shapes, the decision tree, the right reading list, and the ability to state your state invariant out loud.

If you want a companion refresh on the BFS vs DFS decision specifically, work through the traversal problems below and name your state invariant before you write a line.