Graphs
Data structuresHigh priority~1.5 hVertices joined by edges — model relationships, then traverse with BFS, DFS, or a shortest-path engine.
Definition
A graph is a set of vertices (nodes) joined by edges. Edges may be directed (a one-way a → b) or undirected (a two-way a — b), and weighted (each edge carries a cost) or unweighted. Almost every relationship problem is a graph in disguise: a road map, a dependency list, a social network, a state machine, even a 2-D grid (each cell a vertex, each orthogonal step an edge).
Two representations dominate. An adjacency list stores, per vertex, the list of its neighbours — O(V + E) space, the right choice for the sparse graphs interviews almost always use. An adjacency matrix is a V × V grid where m[i][j] marks an edge — O(V²) space but O(1) edge lookup, worth it only for dense graphs. The grid problems in this chapter are implicit graphs: you never build an adjacency list at all, you just compute a cell's four neighbours on the fly.
Operations
| Operation | Average | Worst | Note |
|---|---|---|---|
| build adjacency list | O(V + E) | O(V + E) | One pass over the edges; space is O(V + E) too. |
| BFS / DFS traversal | O(V + E) | O(V + E) | Every vertex and every edge is visited once, given a visited set. |
| shortest path (unweighted) | O(V + E) | O(V + E) | BFS: the first time a vertex is dequeued is along a shortest path. |
| shortest path (non-negative weights) | O(n log n) | O(n log n) | Dijkstra with a binary heap is O(E log V); relax each edge, settle each vertex once. |
| topological sort / cycle check | O(V + E) | O(V + E) | Kahn's in-degree BFS or DFS with a recursion-stack colour. |
| connected components / union | O(1) | O(1) | Union-Find with path compression + union by rank is ≈ O(α(V)) per op — inverse Ackermann, effectively constant. |
| minimum spanning tree | O(n log n) | O(n log n) | Prim's (heap) or Kruskal's (sort + union-find) over the edges is O(E log V). |
When to use
Reach for a graph the moment a problem is about entities and the connections between them, even when the word "graph" never appears. Tell-tales: "connected", "reachable", "shortest path / fewest steps", "depends on / must come before", "groups / regions / provinces / islands", "cycle", "network". A 2-D grid where you move between adjacent cells is the most common disguise.
Once you've spotted the graph, the question picks the tool. Fewest steps in an unweighted graph → BFS. Just need to visit / fill a region, or detect a cycle → DFS. Shortest path with edge costs → Dijkstra. "Can this ordering be done / is there a cycle" over dependencies → topological sort. How many separate groups, or are two things in the same group → Union-Find. Cheapest way to connect everything → a minimum spanning tree.
Techniques
BFS (breadth-first search) — a queue explores the graph in rings of equal distance from the source. Because it reaches every vertex by a shortest number of edges first, BFS is the go-to for shortest path in an unweighted graph (word ladder, fewest moves) and for multi-source spread, where you seed the queue with all sources at once and each ring is one time step (rotting oranges).
DFS (depth-first search) — recursion (or an explicit stack) plunges down one path before backtracking. It's the natural fit for flood-fill / region problems (number of islands), connectivity, and cycle detection in a directed graph (a back-edge to a node still on the recursion stack). Pair it with memoisation when subpaths are reused — a DP over a DAG (longest increasing path).
Topological sort — orders a directed acyclic graph so every edge points forward. Kahn's algorithm repeatedly removes a node with in-degree 0; if fewer than V nodes come out, a cycle blocked it — which is exactly how course schedule answers "can all the courses be finished?".
Dijkstra — a min-priority-queue Greedy that settles the nearest unsettled vertex and relaxes its edges. It finds shortest paths with non-negative weights (network delay time). With negative edges you'd need Bellman–Ford instead.
Union-Find (disjoint set) — tracks which vertices share a component under a stream of union operations, with near-constant find. It answers "how many groups?" (number of provinces) and powers Kruskal's MST. Prim's is the heap-based MST alternative that grows one tree outward (min cost to connect all points).
Related structures
A tree is just a connected, acyclic graph with V − 1 edges, so every tree traversal is a graph traversal that needs no visited set (there are no cycles to revisit). A trie is a tree whose edges are labelled by characters. The grid problems here lean on the same matrix scanning habits, and the shortest-path and MST variants are really greedy algorithms — Dijkstra, Prim, and Kruskal all repeatedly commit to the locally cheapest safe choice. The BFS queue is a plain stack's FIFO cousin, and Dijkstra's frontier is a heap.
Implementation
// adj: Map<node, node[]> (or an array of arrays for integer-labelled nodes)
// BFS — explores in rings; the level counter is the shortest-path distance.
function bfs(adj, start) {
const visited = new Set([start]);
let queue = [start];
let depth = 0;
while (queue.length > 0) {
const next = [];
for (const node of queue) {
for (const neighbor of adj.get(node) ?? []) {
if (visited.has(neighbor)) continue; // never revisit — this breaks cycles
visited.add(neighbor);
next.push(neighbor);
}
}
queue = next;
depth++; // one full ring = one step farther out
}
}
// DFS — plunges deep first; great for regions, connectivity, and cycle checks.
function dfs(adj, start, visited = new Set()) {
visited.add(start);
for (const neighbor of adj.get(start) ?? []) {
if (!visited.has(neighbor)) dfs(adj, neighbor, visited);
}
}Worked examples
Shortest path through a maze — the most common interview graph is a grid you never explicitly build. Each open cell is a vertex; stepping to an orthogonally adjacent open cell is an edge of weight 1. Because every edge costs the same, BFS finds the fewest-step path: it expands outward ring by ring, so the first time it touches the exit, it arrives by a shortest route.
Take the 4×4 grid below — . is open, # is a wall — starting at the top-left (0,0) and aiming for the bottom-right (3,3). Watch BFS flood outward; the number in each visited cell is the ring it was reached on, i.e. its distance from the start:
BFS over a maze grid — '#' is a wall; each frame floods one more ring outward from (0,0)
BFS begins with only the start cell in the queue, at distance 0.
From (0,0) the open neighbours are (0,1) and — through it next ring — the cells one step away. (1,0) is a wall, so it's skipped.
Ring 2 reaches (2,1) below (1,1). Walls and already-visited cells are never enqueued, which is what stops a cycle.
The frontier fans across the open row 2, reaching (2,2) and (2,3). Each cell keeps the distance of the ring that first found it.
Stepping down from (2,3) lands on the exit (3,3). Because BFS arrives in increasing ring order, this first arrival is along a shortest path — 6 steps from the start.
The bottom-left walls are never reached; if the exit had been fenced like this, BFS would drain the queue without arriving and report it unreachable.
function shortestPath(grid) {
const rows = grid.length, cols = grid[0].length;
const seen = Array.from({ length: rows }, () => new Array(cols).fill(false));
let queue = [[0, 0]];
seen[0][0] = true;
let dist = 0;
while (queue.length > 0) {
const next = [];
for (const [r, c] of queue) {
if (r === rows - 1 && c === cols - 1) return dist; // reached the exit
// The four orthogonal neighbours — the implicit edges of a grid graph.
for (const [nr, nc] of [[r + 1, c], [r - 1, c], [r, c + 1], [r, c - 1]]) {
if (nr < 0 || nc < 0 || nr >= rows || nc >= cols) continue;
if (grid[nr][nc] === '#' || seen[nr][nc]) continue; // wall or already visited
seen[nr][nc] = true;
next.push([nr, nc]);
}
}
queue = next;
dist++; // advanced one ring
}
return -1; // exit never reached
}Each cell enters the queue at most once, so the scan is O(m·n) time and O(m·n) space — the same O(V + E) bound every BFS carries, since a grid has V = m·n cells and E ≈ 4V edges. Swap the FIFO queue for a recursion stack and the same skeleton becomes the flood-fill DFS behind number of islands; the only structural change is queue-vs-stack.
Things to look out for
- Forgetting the visited set. A graph has cycles a tree doesn't — without marking nodes visited, a traversal loops forever. Mark a node visited when you enqueue / first reach it, not when you dequeue it, or the same node gets queued many times.
- Using DFS for a shortest unweighted path. DFS finds a* path, not the shortest one — that's BFS's job. Reaching for DFS here is the classic wrong tool.
- Using BFS/DFS for a shortest weighted path. Once edges carry different costs, the fewest-edges path isn't the cheapest. You need Dijkstra (non-negative weights) or Bellman–Ford (negative allowed)
- Counting diagonals on a grid by accident. "4-directionally adjacent" means up/down/left/right only. Adding the diagonal neighbours silently merges regions that should be separate.
- Directed vs. undirected confusion. In an undirected graph add both
a→bandb→ato the adjacency list. In course-schedule, the edge direction is the prerequisite order — reverse it and the answer flips. - Settling a Dijkstra node twice. A node can sit in the heap under several stale distances; skip it if it's already been settled (its popped distance exceeds its recorded best), or you redo work and can corrupt counts.
Corner cases
- An empty graph (no nodes) or a single isolated node — traversals must return a sensible base answer, not crash.
- A disconnected graph — to cover every node you must restart the traversal from each unvisited node (counting components, 2-colouring across components).
- A self-loop (
a → a) or a multi-edge — a self-loop is a length-1 cycle that cycle-detection must catch. - The target is unreachable — shortest-path and spread problems need an explicit "never arrived" sentinel (
-1,0, orInfinity). - Zero-weight edges in a weighted graph — Dijkstra still works (weights are non-negative), but a plain visited-on-dequeue BFS would mis-order them.
- A grid that is entirely passable (one giant region) — a recursive flood fill can overflow the call stack; prefer an explicit stack or a queue at scale.