Graph Modeling & Implicit Graphs
Why this exists
Most graph problems do not say "graph". They say "transform hit into cog one letter at a time", "a lock has four wheels", "you may stop at most k times", "collect every key", "course b requires course a". The algorithms in the rest of this module — BFS, DFS, topological sort, shortest paths — are short and well known. The hard part, in interviews and in real systems, is the step before them: deciding what a vertex is, what an edge is, and whether the resulting graph is small enough to search. Get the model right and the solution is a textbook algorithm; get it wrong and no amount of clever code rescues it.
The idea is old. Euler's 1736 paper on the bridges of Königsberg is remembered as the first graph theory result precisely because Euler threw away everything about the city except which land masses were joined by which bridges — a modeling step, not an algorithmic one. Artificial intelligence research in the 1950s and 1960s (Newell and Simon's problem-solving programs, the Shakey robot project that produced A* in 1968) formalized state-space search: a puzzle is a graph whose vertices are configurations and whose edges are legal moves, and that graph is usually far too big to write down, so it is generated on demand. Compilers, build systems, package managers, network routers and route planners all run on graphs that someone had to decide how to model.
This lesson is about that decision. You will learn the vocabulary precisely (directed, weighted, multigraph, simple), the four standard representations and what each costs in memory and per operation, a catalogue of modeling patterns (word ladders, locks, sliding puzzles, knight moves, grids, dependencies, bipartite "people vs jobs", time-expanded graphs, layered graphs for "at most k" constraints, product graphs for "state = node plus something"), how to work with graphs that are never stored at all, and how to estimate the size of a state space before writing the search. The Graphs overview introduced adjacency lists and matrices briefly; here we go deeper.
Pattern triggers
| If the problem says or has… | Think of… |
|---|---|
| "transform A into B, one small change per step, fewest steps" | Implicit graph: states are vertices, legal changes are edges, then BFS |
| "minimum number of moves / presses / swaps" on a puzzle or lock | State-space graph; estimate the state count first |
| A 2D grid with walls, "4-directionally adjacent" | Grid graph: cell = vertex, neighbour step = edge, no adjacency list needed |
| "course b requires course a", "task x before task y", build or import order | Directed dependency graph (a DAG if valid) |
| "assign people to jobs", "stops and routes", two kinds of things | Bipartite graph between the two kinds |
| "at most k stops / k edges / k discounts / k removals" | Layered (product) graph: state = (node, how many used) |
| "collect all keys", "visit every node", "with fuel f", "carrying item x" | Product graph: state = (node, mask / fuel / inventory) |
| Edges that only exist at certain times, waiting allowed, periodic schedules | Time-expanded graph: state = (node, time) or (node, time mod period) |
| "two types of edges must alternate", "parity matters" | Product with a small label: state = (node, last colour / parity) |
| and "visit all" | Bitmask states: |
| up to or more, up to a few | Adjacency list or CSR, never a matrix |
| a few thousand and frequent "is there an edge u-v?" | Adjacency matrix (or bitset rows) |
| "process edges in order of weight" | Edge list (sort it) |
The meta-trigger: the problem asks for a minimum count, a reachability answer or an ordering, and the thing that changes from step to step can be captured in a finite, hashable state. Once you can name the state, you have a graph.
Intuition & first principles
The vocabulary, precisely
A graph is a set of vertices (nodes) and a set of edges , each edge joining two vertices. We write and (or simply and inside big-O, which is the convention in CLRS).
- Undirected: an edge can be traversed both ways (friendship, a two-way road). Directed: an edge goes from to only (follows, one-way streets, "a must precede b"). An undirected graph is equivalent to a directed graph that has both and ; that is how almost all code stores it, so an undirected graph with edges occupies adjacency entries.
- Weighted: each edge carries a number — length, cost, time, capacity, probability. Unweighted graphs can be read as every edge having weight 1, which is why BFS computes shortest paths in them.
- Simple: no self-loops (edge from to ) and no parallel edges. A multigraph allows parallel edges (two flights between the same cities with different prices) and sometimes loops. Algorithms mostly don't care, but counting arguments do: a simple undirected graph has at most edges, a multigraph has no bound.
- Degree: number of edges at a vertex; in directed graphs, in-degree and out-degree. The handshake lemma: in an undirected graph, the degrees sum to , because every edge contributes 1 to each of its two endpoints. It is the reason "iterate over every vertex's neighbours" costs and not .
- Sparse vs dense: informally, sparse means or (roads, the web, social graphs, grids), dense means (complete graphs, distance matrices). Real-world graphs are overwhelmingly sparse: a road network with intersections has an average degree under 3.
- Path, cycle, connected, strongly connected (directed: every vertex reaches every other), DAG (directed acyclic graph), tree (connected, acyclic, exactly edges), bipartite (vertices split into two sides, every edge crosses).
The modeling question
Every modeling decision is an answer to three questions:
- What is a state? The minimal information that, together with the rules, determines what can happen next. For a lock it is the four digits. For a grid walk with keys it is the cell and the set of keys held, because two visits to the same cell with different keys have different futures.
- What is a move? Each legal transition from one state to another is an edge. If moves have different costs, the edges are weighted.
- What is asked? Fewest moves (BFS), cheapest moves (Dijkstra or 0-1 BFS), whether reachable (any traversal), an order (topological sort), a grouping (components), a pairing (matching).
The test that a state is complete is the Markov property: the future depends only on the state, not on how you got there. If two different histories leading to "the same" state can have different futures, your state is missing a component. The test that a state is minimal is the opposite: if two states always have identical futures, merge them, because every redundant component multiplies the state count.
The single most useful habit
Before writing any search, write down state = (...), then compute the number of possible states as a product of the ranges of the components. If that number is below roughly , a BFS over it is usually fine in C++ or Java and borderline-but-possible in Python ( is comfortable there). If it is , you need a different idea, not faster code.
Explicit vs implicit
An explicit graph is given as data: an edge list in the input, a table in a database. An implicit graph is given as a rule: a function neighbours(state) that generates the outgoing edges of a state on demand. The lock has states and directed edges; you never build an adjacency list for it, you compute the 8 neighbours of "0000" when you dequeue it. A chess engine's game tree, a SAT solver's search, a route planner's "road graph with turn restrictions" are implicit graphs of astronomical size, explored partially.
The search algorithms do not care which kind they get. BFS needs three things: a start state, a way to enumerate neighbours, and a way to remember which states it has seen (a hash set or an array indexed by an encoding of the state). That is the whole interface.
Mechanics
The four representations
flowchart LR
G["Graph: 4 vertices, 6 directed edges"] --> EL["Edge list: [(0,1),(0,2),(2,0),(1,2),(2,3),(3,1)]"]
G --> AL["Adjacency list: 0 to [1,2], 1 to [2], 2 to [0,3], 3 to [1]"]
G --> AM["Adjacency matrix: 4 x 4 booleans"]
G --> CSR["CSR: offsets [0,2,3,5,6] + targets [1,2,2,0,3,1]"]
Edge list. An array of (u, v) or (u, v, w) tuples. Memory . Answering "who are the neighbours of ?" requires scanning all edges, so it is useless for traversal, but it is the natural form for algorithms that process edges globally: Kruskal's MST sorts it (see minimum spanning trees), Bellman-Ford relaxes every edge per round, and union-find connectivity streams it. It is also the usual input format, from which you build one of the others.
Adjacency list. For each vertex, a dynamic array (or linked list) of its neighbours. Memory . Iterating over a vertex's neighbours costs , so a full traversal costs . Testing "is an edge?" costs unless you use a hash set per vertex. This is the default for sparse graphs and for anything you will traverse. Its weakness is constant factors: each vertex's array is a separate heap allocation, so a traversal jumps around memory, and in Java or Python every neighbour may be a boxed object.
Adjacency matrix. An table, M[u][v] = 1 (or the weight) if the edge exists. Memory regardless of . Edge test is ; enumerating neighbours costs per vertex, so a traversal costs even if the graph has 10 edges. Good for dense graphs, small , Floyd-Warshall (which needs the matrix anyway), and bitset tricks: with one bit per cell, "common neighbours of and " is the popcount of an AND of two rows, word operations.
Compressed sparse row (CSR). Two flat arrays: targets, all adjacency lists concatenated in vertex order, and offsets of length , where vertex 's neighbours are targets[offsets[u] : offsets[u+1]]. Memory: integers, nothing else — no per-vertex objects, no pointers. Neighbour iteration is a contiguous scan, which is why CSR is the format of choice in high-performance graph libraries, sparse linear algebra (where it is literally the sparse-matrix format of the same name) and GPU graph processing. Its weakness: it is static. Adding an edge means rebuilding or shifting, so build it once from an edge list after all edges are known.
Costs side by side
| Operation | Edge list | Adjacency list | Adjacency matrix | CSR |
|---|---|---|---|---|
| Memory | ints | |||
| Neighbours of | , contiguous | |||
| Is an edge? | , expected with hash sets | if each row is sorted | ||
| Add edge | amortized | rebuild | ||
| Remove edge | rebuild | |||
| Full traversal (BFS/DFS) | naive | , best constants | ||
| Typical use | Kruskal, Bellman-Ford, input | Default for traversal | Dense, Floyd-Warshall, bitsets | Large static graphs |
Concrete numbers settle most choices. With vertices, a byte-per-cell matrix needs bytes, 10 GB; even a bit matrix needs 1.25 GB. With undirected edges ( adjacency entries), CSR in 32-bit integers needs MB. Measured in CPython 3.14 on this exact case (random edges), a list-of-lists adjacency took about 25 MB of list objects and pointers — and that is not counting the integer objects themselves, which happened to be shared with the edge list — while CSR built in array('i') took 8.4 MB. In Java, List<List<Integer>> pays for an Integer object per neighbour (typically 16 bytes on a 64-bit JVM with compressed pointers, except for the cached values −128..127) plus a 4-byte reference and per-list overhead — several times the 4 bytes per entry of an int[] CSR.
Building CSR by hand
CSR is built in two passes, a counting sort by source vertex (the same counting idea as in non-comparison sorts). Take and the directed edges (0,1), (0,2), (2,0), (1,2), (2,3), (3,1).
- Count out-degrees into
count[u + 1]:[0, 2, 1, 2, 1]. - Prefix-sum it to get
offsets = [0, 2, 3, 5, 6]. Vertex 2's neighbours will live intargets[3:5]. - Copy
offsets[0..n-1]into a write cursorpos, then place each edge attargets[pos[u]]and advancepos[u].
The trace below was produced by running exactly that loop.
| Step | Edge placed | pos after | targets after |
|---|---|---|---|
| 0 | — | [0, 2, 3, 5] | [_, _, _, _, _, _] |
| 1 | (0, 1) | [1, 2, 3, 5] | [1, _, _, _, _, _] |
| 2 | (0, 2) | [2, 2, 3, 5] | [1, 2, _, _, _, _] |
| 3 | (2, 0) | [2, 2, 4, 5] | [1, 2, _, 0, _, _] |
| 4 | (1, 2) | [2, 3, 4, 5] | [1, 2, 2, 0, _, _] |
| 5 | (2, 3) | [2, 3, 5, 5] | [1, 2, 2, 0, 3, _] |
| 6 | (3, 1) | [2, 3, 5, 6] | [1, 2, 2, 0, 3, 1] |
At the end pos[u] == offsets[u + 1] for every , which is the check that every slot was filled exactly once. Neighbours of 2: targets[3:5] = [0, 3]. Because the placement pass visits edges in input order, each row keeps the input order (the sort is stable); sort each row afterwards if you want binary-search edge tests.
A modeling pipeline
Every modeling problem follows the same pipeline. The diagram is the checklist I run through before writing code.
flowchart TD
P["Problem statement"] --> S["Name the state: what determines the future?"]
S --> M["Name the moves: legal transitions and their costs"]
M --> C["Count states: product of component ranges"]
C -->|"too many"| R["Shrink the state: symmetry, dominance, better encoding"]
R --> C
C -->|"fits in memory and time"| Q["Pick the query algorithm"]
Q --> B["Unit costs: BFS"]
Q --> Z["Costs 0 or 1: 0-1 BFS"]
Q --> D["Non-negative costs: Dijkstra"]
Q --> O["Order or cycles: topological sort or DFS"]
The pattern catalogue
Word ladder. Words are vertices; two words are adjacent if they differ in exactly one position. "Shortest transformation sequence" is a BFS shortest path. Two ways to generate edges: compare all pairs of words ( for words of length ; with , that is character comparisons), or, for each word, try all single-letter substitutions and look each up in a hash set ( including hashing, about character operations). A third way groups words by wildcard patterns (h*t matches hot and hit): words sharing a pattern form a clique, and connecting each word to its pattern nodes instead of to each other turns a clique of size ( edges) into a star ( edges). That "replace a clique with a hub vertex" trick recurs everywhere.
Lock combinations. Four wheels with digits 0–9; a move turns one wheel one notch either way. State = the 4-digit string; states; each has exactly 8 neighbours. Dead-ends are vertices you delete. BFS from "0000". Without dead-ends, the farthest combination is 20 moves away (each wheel at most 5 notches; checked by BFS).
Sliding puzzles. State = the arrangement of tiles, encoded as a string or a base- integer; moves = slide a tile into the blank. The 2×3 puzzle has arrangements, of which exactly half, 360, are reachable from any given one (a parity invariant splits the permutations into two classes); the hardest reachable 2×3 position is 21 moves from solved. The 3×3 "8-puzzle" has reachable states and a diameter of 31 moves. The 4×4 "15-puzzle" has reachable states — plain BFS over that is hopeless and solvers use A* or IDA* with pattern-database heuristics. Those three numbers are the best illustration I know of why you estimate before you search: same rules, three sizes, three different algorithms.
Knight moves. State = square; edges = the up-to-8 knight jumps. On an board, states, at most edges. On an unbounded board you bound the search region instead: by symmetry you can fold the target into the first quadrant, and the standard solutions to the infinite-board version allow the search to step only a small margin (two squares) outside the box spanned by the start and the target. Treat that margin as a known result for this specific puzzle, not a general rule; when in doubt, make the box generously larger and let BFS confirm.
Grids. Each cell is a vertex, adjacent open cells are joined. You never build adjacency lists for a grid: the neighbours of (r, c) are computed with a direction array, and "visited" is a 2D boolean array or a flat array indexed by r * C + c. The matrices and grids lesson covers direction arrays, bounds checks and flattening. Grids hide variations: 8-connectivity, diagonal costs, teleporters (extra edges), one-way conveyor cells (directed edges), cells with costs (weighted).
Dependency graphs. "Course b requires a" is the directed edge a → b (do a first). A valid schedule is a topological order; impossibility is a directed cycle, detectable by DFS. Package managers, build systems (Make, Bazel), spreadsheet recalculation and database migration tools all model their work this way. A subtle choice: the arrow direction. a → b meaning "a before b" gives Kahn's algorithm its natural form; the reverse, "b depends on a", is what a build tool stores. Both are fine; mixing them is the bug.
Bipartite "people vs jobs". When the problem has two kinds of entities and relationships only between kinds — workers and tasks, students and projects, bus stops and bus routes — use one vertex per entity and edges across. Matching problems live here (bipartite matching). The bus-routes problem shows the modeling payoff: connecting every pair of stops on the same route creates a clique per route (a route with stops gives edges), while a bipartite graph of stops and routes has one edge per (stop, route) membership — edges total — and the answer "fewest buses" is half the BFS distance in it.
Time-expanded graphs. When edges exist only at certain times (a train departs at 9:05), or waiting is a choice, make time part of the state: vertex , edges for each departure and for waiting. Public-transit routers built on this idea (and its compressed cousins) answer timetable queries. If the schedule is periodic with period , use to keep the state space finite.
Layered graphs for "at most k". The constraint "at most stops" breaks plain shortest-path algorithms, because the cheapest path to an intermediate city might use too many stops while a pricier path with fewer stops is the one that extends to the answer. Fix: state = (city, edges used so far). Make copies (layers) of the city set; an edge becomes for every layer . Now "at most stops" is "reach any copy of the destination in layers ", an ordinary shortest-path query on a DAG of layers. The same pattern handles "at most discount coupons" (two kinds of edges: normal , discounted ) and "remove at most obstacles".
flowchart LR
subgraph L0["layer 0: no flights yet"]
a0["0"]
end
subgraph L1["layer 1: one flight"]
b1["1"]
end
subgraph L2["layer 2: two flights"]
c2["2"]
d2["3"]
end
a0 -->|"100"| b1
b1 -->|"100"| c2
b1 -->|"600"| d2
In the flights example below ( stop, so at most 2 flights), the cheapest route costs 400 but needs 3 flights; in the layered graph it would end in layer 3, outside the allowed range, so the answer is the layer-2 route at 700.
Product graphs. Layered graphs are a special case of a general construction: if the problem's "extra information" takes values in a finite set (keys held, fuel left, last edge colour, parity, direction faced), the state space is , and the edges are the original edges annotated with how they change the extra information. Collecting keys in a grid: state = (row, col, key mask), states. Visiting all nodes of a small graph: state = (current node, set visited), . Alternating red/blue edges: state = (node, colour of the last edge), . Fuel: state = (city, fuel), with refuelling edges inside a city. Formally this is the tensor product of the graph with a finite automaton tracking the extra information — the same construction compilers use to intersect a control-flow graph with a property automaton, and that regular-path queries in graph databases use.
The ladder: brute force → better → optimal
The ladder for a modeling topic is a ladder of models, not of loops. Take one problem through it: cheapest flights from src to dst using at most k stops (LeetCode 787, cities).
Rung 1: enumerate paths
DFS over all simple paths of at most flights, track the cheapest that ends at dst. Correct, but the number of paths grows like for average out-degree ; with cities and a dense flight table that is , hopeless beyond . Time exponential, space .
Rung 2: plain Dijkstra on cities
Treat it as an ordinary shortest-path problem and ignore , or stop Dijkstra when a path has too many stops. Wrong: Dijkstra keeps only the cheapest label per city, and the cheapest way to reach an intermediate city may use too many stops, while the path that should win arrives there with a worse price but fewer stops — and gets discarded. The state "city" violates the Markov property: two arrivals at city 2, one after 1 flight and one after 3, have different futures.
Rung 3: layered graph (Bellman-Ford with rounds)
State = (city, flights used). Layer holds the cheapest cost to reach each city with at most flights. Layer is computed from layer by relaxing every flight once, reading only from layer (this is exactly rounds of Bellman-Ford with a copied array). Time , space for two layers. With and flights, at most relaxations. Correct by construction, because the model is right.
Rung 4: Dijkstra on the product graph
Run Dijkstra on states (city, stops), of them. It finishes as soon as a state with the destination is popped, which can be much faster than full rounds when the answer is cheap and the graph is big, at the cost of memory and a heap. Time worst case.
| Rung | Model | Time | Space | Correct? | Why it improves |
|---|---|---|---|---|---|
| 1 | All paths, DFS | Yes | Baseline | ||
| 2 | City only, Dijkstra | No | Fast but the state is incomplete | ||
| 3 | Layers (city, flights), Bellman-Ford rounds | Yes | Complete state; each layer only depends on the previous one | ||
| 4 | Product graph, Dijkstra | Yes | Early exit; better when far fewer states are reached than exist |
The lesson generalizes: rung 2's failure is the most common modeling bug in graph problems. When a shortest-path algorithm gives a wrong answer on a constrained problem, the first suspect is a state that is missing a component.
Correctness
Why a product graph is exact
Claim: if the state captures everything that determines which moves are legal and what they cost, then shortest paths in the product graph correspond exactly to optimal solutions of the original problem.
Proof sketch. Define a bijection between valid move sequences of the original problem and paths in the product graph starting at the initial state: a sequence of moves from the start produces states , and each step is, by construction, an edge of the product graph with the same cost as the move. Conversely, every path in the product graph is a sequence of legal moves, because an edge exists only if the move is legal in that state, and legality depends only on the state (the Markov property). The bijection preserves total cost, so a minimum-cost path to any goal state is a minimum-cost valid solution. If the state were incomplete — say we dropped the key mask — there would be product-graph paths that use a door without its key, the map from paths to solutions would not be onto valid solutions, and the shortest path could be invalid.
Why the layered flights algorithm is right
Let be the minimum cost of a route from src to with at most flights. Invariant: after round , the array cur equals .
- Base: before any round,
cur[src] = 0and every other entry is ; that is . - Step: a route with at most flights to either has at most flights (cost ) or ends with a flight of cost preceded by a route with at most flights to (cost ). So . Round computes exactly this provided it reads only round- values — hence the copy. Updating in place can read a value already improved in this round, which is a route with flights sneaking in.
After rounds, cur[dst] is , the answer. On the example below, an in-place single round already reaches city 3 at cost 400 using 3 flights — the exact bug the copy prevents.
Why the CSR build fills every slot exactly once
After the prefix sum, offsets[u] is the number of edges whose source is less than , so the slots are disjoint, cover , and have length . The placement pass writes edge number out of to offsets[u] + j, and ranges over . So each slot is written once, and at the end pos[u] = offsets[u + 1].
Complexity
Representations. Covered in the cost table above. Two refinements matter in practice:
- Cache behaviour. A BFS over CSR reads
targetssequentially within each row andoffsetswith good locality; a BFS over a list-of-lists follows a pointer per vertex to a separately allocated array. On graphs larger than the CPU caches, CSR traversals are commonly several times faster for the same asymptotic work. Graph frameworks also reorder vertices (by BFS order, degree, or community) so that neighbours have nearby ids and thevisitedarray accesses become local. - Hashing costs. In implicit graphs, the
visitedstructure is usually a hash set of states. Hashing a string state of length costs , which is why word-ladder neighbour generation is per word, not . Encoding a state as a small integer (base-10 digits for the lock, base- for puzzles, bitmasks for sets) turns the hash set into a flat array and removes that factor.
Search over a modeled graph. Whatever algorithm you run afterwards, its cost is in terms of the modeled graph's size. For BFS that is where is the set of states reached and the transitions examined. For a product graph with original degree , . Space is dominated by the visited structure, .
Estimating before searching. Multiply the component ranges, then multiply by the branching factor for edges:
| Problem | State | States | Edges per state | Verdict |
|---|---|---|---|---|
| Open the lock | 4 digits | 8 | Trivial | |
| 2×3 sliding puzzle | permutation of 6 | 720 (360 reachable) | ≤ 3 | Trivial |
| 8-puzzle | permutation of 9 | 362,880 (181,440 reachable) | ≤ 4 | Easy in any language |
| 15-puzzle | permutation of 16 | ( reachable) | ≤ 4 | BFS impossible; IDA* + heuristic |
| Keys in a 30×30 grid, 6 keys | (r, c, mask) | 4 | Easy | |
| Visit all of 12 nodes | (node, mask) | ≤ 11 | Easy | |
| 40×40 grid, remove up to 1600 obstacles | (r, c, removals left) | 4 | Fine in C++/Java, slow in Python; note any makes the obstacles irrelevant | |
| Flights, , | (city, flights) | ≤ 99 | Easy |
A useful calibration: a tight C++ BFS processes on the order of – edge relaxations per second; CPython manages roughly – simple dictionary operations per second. Divide the edge count by those rates and you know whether you are in seconds or in years. (These rates are rough and machine-dependent; measure on your own hardware with the Module 0 capstone.)
Implementation
Building every representation from an edge list
One program builds all four representations of the example graph and checks that they agree. It also builds the undirected version to show the handshake lemma and the multigraph effect (the edges (0,2) and (2,0) become two parallel undirected edges).
from array import array
def build_adj_list(n, edges, directed=True):
adj = [[] for _ in range(n)]
for u, v in edges:
adj[u].append(v)
if not directed:
adj[v].append(u)
return adj
def build_matrix(n, edges, directed=True):
mat = [[0] * n for _ in range(n)]
for u, v in edges:
mat[u][v] += 1 # counts parallel edges
if not directed:
mat[v][u] += 1
return mat
def build_csr(n, edges, directed=True):
"""Two-pass counting build. Returns (offsets, targets)."""
arcs = edges if directed else edges + [(v, u) for u, v in edges]
offsets = array("i", [0]) * (n + 1)
for u, _ in arcs:
offsets[u + 1] += 1
for i in range(n):
offsets[i + 1] += offsets[i]
targets = array("i", [0]) * len(arcs)
pos = array("i", offsets[:n])
for u, v in arcs:
targets[pos[u]] = v
pos[u] += 1
return offsets, targets
def csr_neighbours(offsets, targets, u):
return targets[offsets[u]:offsets[u + 1]]
if __name__ == "__main__":
n = 4
edges = [(0, 1), (0, 2), (2, 0), (1, 2), (2, 3), (3, 1)]
adj = build_adj_list(n, edges)
mat = build_matrix(n, edges)
off, tgt = build_csr(n, edges)
assert list(off) == [0, 2, 3, 5, 6]
assert list(tgt) == [1, 2, 2, 0, 3, 1]
for u in range(n):
from_matrix = [v for v in range(n) if mat[u][v]]
assert sorted(adj[u]) == sorted(csr_neighbours(off, tgt, u)) == from_matrix
assert mat[3][1] == 1 and mat[1][3] == 0 # directed
# Undirected multigraph: degrees sum to 2m (handshake lemma).
uadj = build_adj_list(n, edges, directed=False)
degrees = [len(uadj[u]) for u in range(n)]
assert degrees == [3, 3, 4, 2] and sum(degrees) == 2 * len(edges)
umat = build_matrix(n, edges, directed=False)
assert umat[0][2] == 2 # two parallel edges 0-2
uoff, _ = build_csr(n, edges, directed=False)
assert [uoff[u + 1] - uoff[u] for u in range(n)] == degrees
print("representations OK")
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class Representations {
static List<List<Integer>> buildAdjList(int n, int[][] edges, boolean directed) {
List<List<Integer>> adj = new ArrayList<>();
for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
for (int[] e : edges) {
adj.get(e[0]).add(e[1]);
if (!directed) adj.get(e[1]).add(e[0]);
}
return adj;
}
static int[][] buildMatrix(int n, int[][] edges, boolean directed) {
int[][] mat = new int[n][n];
for (int[] e : edges) {
mat[e[0]][e[1]]++;
if (!directed) mat[e[1]][e[0]]++;
}
return mat;
}
/** Returns {offsets, targets}. */
static int[][] buildCsr(int n, int[][] edges, boolean directed) {
int m = directed ? edges.length : 2 * edges.length;
int[] us = new int[m], vs = new int[m];
for (int i = 0; i < edges.length; i++) {
us[i] = edges[i][0]; vs[i] = edges[i][1];
if (!directed) { us[edges.length + i] = edges[i][1]; vs[edges.length + i] = edges[i][0]; }
}
int[] offsets = new int[n + 1];
for (int i = 0; i < m; i++) offsets[us[i] + 1]++;
for (int i = 0; i < n; i++) offsets[i + 1] += offsets[i];
int[] targets = new int[m];
int[] pos = Arrays.copyOf(offsets, n);
for (int i = 0; i < m; i++) targets[pos[us[i]]++] = vs[i];
return new int[][] {offsets, targets};
}
static void check(boolean ok, String msg) { if (!ok) throw new AssertionError(msg); }
public static void main(String[] args) {
int n = 4;
int[][] edges = {{0, 1}, {0, 2}, {2, 0}, {1, 2}, {2, 3}, {3, 1}};
List<List<Integer>> adj = buildAdjList(n, edges, true);
int[][] mat = buildMatrix(n, edges, true);
int[][] csr = buildCsr(n, edges, true);
int[] off = csr[0], tgt = csr[1];
check(Arrays.equals(off, new int[] {0, 2, 3, 5, 6}), "offsets");
check(Arrays.equals(tgt, new int[] {1, 2, 2, 0, 3, 1}), "targets");
for (int u = 0; u < n; u++) {
List<Integer> a = new ArrayList<>(adj.get(u));
List<Integer> c = new ArrayList<>();
for (int i = off[u]; i < off[u + 1]; i++) c.add(tgt[i]);
List<Integer> fromMatrix = new ArrayList<>();
for (int v = 0; v < n; v++) if (mat[u][v] > 0) fromMatrix.add(v);
a.sort(null); c.sort(null);
check(a.equals(c) && a.equals(fromMatrix), "neighbours of " + u);
}
check(mat[3][1] == 1 && mat[1][3] == 0, "directed");
List<List<Integer>> uadj = buildAdjList(n, edges, false);
int[] degrees = new int[n];
int sum = 0;
for (int u = 0; u < n; u++) { degrees[u] = uadj.get(u).size(); sum += degrees[u]; }
check(Arrays.equals(degrees, new int[] {3, 3, 4, 2}) && sum == 2 * edges.length, "handshake");
check(buildMatrix(n, edges, false)[0][2] == 2, "parallel edges");
int[] uoff = buildCsr(n, edges, false)[0];
for (int u = 0; u < n; u++) check(uoff[u + 1] - uoff[u] == degrees[u], "csr degree");
System.out.println("representations OK");
}
}
#include <algorithm>
#include <cassert>
#include <iostream>
#include <utility>
#include <vector>
using Edges = std::vector<std::pair<int, int>>;
std::vector<std::vector<int>> buildAdjList(int n, const Edges& edges, bool directed) {
std::vector<std::vector<int>> adj(n);
for (auto [u, v] : edges) {
adj[u].push_back(v);
if (!directed) adj[v].push_back(u);
}
return adj;
}
std::vector<std::vector<int>> buildMatrix(int n, const Edges& edges, bool directed) {
std::vector<std::vector<int>> mat(n, std::vector<int>(n, 0));
for (auto [u, v] : edges) {
++mat[u][v];
if (!directed) ++mat[v][u];
}
return mat;
}
struct Csr {
std::vector<int> offsets, targets;
};
Csr buildCsr(int n, const Edges& edges, bool directed) {
Edges arcs = edges;
if (!directed)
for (auto [u, v] : edges) arcs.emplace_back(v, u);
Csr g;
g.offsets.assign(n + 1, 0);
for (auto [u, v] : arcs) ++g.offsets[u + 1];
for (int i = 0; i < n; ++i) g.offsets[i + 1] += g.offsets[i];
g.targets.assign(arcs.size(), 0);
std::vector<int> pos(g.offsets.begin(), g.offsets.begin() + n);
for (auto [u, v] : arcs) g.targets[pos[u]++] = v;
return g;
}
int main() {
int n = 4;
Edges edges = {{0, 1}, {0, 2}, {2, 0}, {1, 2}, {2, 3}, {3, 1}};
auto adj = buildAdjList(n, edges, true);
auto mat = buildMatrix(n, edges, true);
Csr g = buildCsr(n, edges, true);
assert((g.offsets == std::vector<int>{0, 2, 3, 5, 6}));
assert((g.targets == std::vector<int>{1, 2, 2, 0, 3, 1}));
for (int u = 0; u < n; ++u) {
std::vector<int> a = adj[u];
std::vector<int> c(g.targets.begin() + g.offsets[u], g.targets.begin() + g.offsets[u + 1]);
std::vector<int> fromMatrix;
for (int v = 0; v < n; ++v)
if (mat[u][v]) fromMatrix.push_back(v);
std::sort(a.begin(), a.end());
std::sort(c.begin(), c.end());
assert(a == c && a == fromMatrix);
}
assert(mat[3][1] == 1 && mat[1][3] == 0);
auto uadj = buildAdjList(n, edges, false);
std::vector<int> degrees;
int sum = 0;
for (auto& row : uadj) { degrees.push_back(static_cast<int>(row.size())); sum += static_cast<int>(row.size()); }
assert((degrees == std::vector<int>{3, 3, 4, 2}) && sum == 2 * static_cast<int>(edges.size()));
assert(buildMatrix(n, edges, false)[0][2] == 2);
Csr ug = buildCsr(n, edges, false);
for (int u = 0; u < n; ++u) assert(ug.offsets[u + 1] - ug.offsets[u] == degrees[u]);
std::cout << "representations OK\n";
}
type Edge = [number, number];
function buildAdjList(n: number, edges: Edge[], directed = true): number[][] {
const adj: number[][] = Array.from({ length: n }, () => []);
for (const [u, v] of edges) {
adj[u].push(v);
if (!directed) adj[v].push(u);
}
return adj;
}
function buildMatrix(n: number, edges: Edge[], directed = true): number[][] {
const mat = Array.from({ length: n }, () => new Array<number>(n).fill(0));
for (const [u, v] of edges) {
mat[u][v] += 1;
if (!directed) mat[v][u] += 1;
}
return mat;
}
function buildCsr(n: number, edges: Edge[], directed = true): { offsets: Int32Array; targets: Int32Array } {
const arcs: Edge[] = directed ? edges : [...edges, ...edges.map(([u, v]): Edge => [v, u])];
const offsets = new Int32Array(n + 1);
for (const [u] of arcs) offsets[u + 1]++;
for (let i = 0; i < n; i++) offsets[i + 1] += offsets[i];
const targets = new Int32Array(arcs.length);
const pos = offsets.slice(0, n);
for (const [u, v] of arcs) targets[pos[u]++] = v;
return { offsets, targets };
}
function assert(ok: boolean, msg: string): void {
if (!ok) throw new Error(msg);
}
const n = 4;
const edges: Edge[] = [[0, 1], [0, 2], [2, 0], [1, 2], [2, 3], [3, 1]];
const adj = buildAdjList(n, edges);
const mat = buildMatrix(n, edges);
const { offsets, targets } = buildCsr(n, edges);
assert(Array.from(offsets).join() === "0,2,3,5,6", "offsets");
assert(Array.from(targets).join() === "1,2,2,0,3,1", "targets");
for (let u = 0; u < n; u++) {
const a = [...adj[u]].sort((x, y) => x - y).join();
const c = Array.from(targets.slice(offsets[u], offsets[u + 1])).sort((x, y) => x - y).join();
const m = [...Array(n).keys()].filter((v) => mat[u][v] > 0).join();
assert(a === c && a === m, `neighbours of ${u}`);
}
assert(mat[3][1] === 1 && mat[1][3] === 0, "directed");
const uadj = buildAdjList(n, edges, false);
const degrees = uadj.map((row) => row.length);
assert(degrees.join() === "3,3,4,2" && degrees.reduce((s, d) => s + d, 0) === 2 * edges.length, "handshake");
assert(buildMatrix(n, edges, false)[0][2] === 2, "parallel edges");
const uoff = buildCsr(n, edges, false).offsets;
for (let u = 0; u < n; u++) assert(uoff[u + 1] - uoff[u] === degrees[u], "csr degree");
console.log("representations OK");
Layered graph: cheapest flights with at most k stops
Layer is "cheapest cost using at most flights". Each round reads the previous layer only. Test data: LeetCode 787's two published examples plus an unreachable case.
def cheapest_within_k_stops(n, flights, src, dst, k):
INF = float("inf")
cur = [INF] * n
cur[src] = 0
for _ in range(k + 1): # at most k stops = at most k + 1 flights
nxt = cur[:] # next layer starts as "at most i flights"
for u, v, w in flights:
if cur[u] != INF and cur[u] + w < nxt[v]:
nxt[v] = cur[u] + w # read layer i, write layer i + 1
cur = nxt
return -1 if cur[dst] == INF else cur[dst]
if __name__ == "__main__":
f1 = [[0, 1, 100], [1, 2, 100], [2, 0, 100], [1, 3, 600], [2, 3, 200]]
assert cheapest_within_k_stops(4, f1, 0, 3, 1) == 700
assert cheapest_within_k_stops(4, f1, 0, 3, 2) == 400
f2 = [[0, 1, 100], [1, 2, 100], [0, 2, 500]]
assert cheapest_within_k_stops(3, f2, 0, 2, 1) == 200
assert cheapest_within_k_stops(3, f2, 0, 2, 0) == 500
assert cheapest_within_k_stops(3, [[0, 1, 5]], 0, 2, 5) == -1
print("layered flights OK")
import java.util.Arrays;
public class CheapestFlights {
static int cheapestWithinKStops(int n, int[][] flights, int src, int dst, int k) {
final int INF = Integer.MAX_VALUE;
int[] cur = new int[n];
Arrays.fill(cur, INF);
cur[src] = 0;
for (int round = 0; round <= k; round++) {
int[] nxt = cur.clone();
for (int[] f : flights) {
int u = f[0], v = f[1], w = f[2];
if (cur[u] != INF && cur[u] + w < nxt[v]) nxt[v] = cur[u] + w;
}
cur = nxt;
}
return cur[dst] == INF ? -1 : cur[dst];
}
static void check(boolean ok) { if (!ok) throw new AssertionError(); }
public static void main(String[] args) {
int[][] f1 = {{0, 1, 100}, {1, 2, 100}, {2, 0, 100}, {1, 3, 600}, {2, 3, 200}};
check(cheapestWithinKStops(4, f1, 0, 3, 1) == 700);
check(cheapestWithinKStops(4, f1, 0, 3, 2) == 400);
int[][] f2 = {{0, 1, 100}, {1, 2, 100}, {0, 2, 500}};
check(cheapestWithinKStops(3, f2, 0, 2, 1) == 200);
check(cheapestWithinKStops(3, f2, 0, 2, 0) == 500);
check(cheapestWithinKStops(3, new int[][] {{0, 1, 5}}, 0, 2, 5) == -1);
System.out.println("layered flights OK");
}
}
#include <cassert>
#include <climits>
#include <iostream>
#include <vector>
int cheapestWithinKStops(int n, const std::vector<std::vector<int>>& flights, int src, int dst, int k) {
const int INF = INT_MAX;
std::vector<int> cur(n, INF);
cur[src] = 0;
for (int round = 0; round <= k; ++round) {
std::vector<int> nxt = cur;
for (const auto& f : flights) {
int u = f[0], v = f[1], w = f[2];
if (cur[u] != INF && cur[u] + w < nxt[v]) nxt[v] = cur[u] + w;
}
cur.swap(nxt);
}
return cur[dst] == INF ? -1 : cur[dst];
}
int main() {
std::vector<std::vector<int>> f1 = {{0, 1, 100}, {1, 2, 100}, {2, 0, 100}, {1, 3, 600}, {2, 3, 200}};
assert(cheapestWithinKStops(4, f1, 0, 3, 1) == 700);
assert(cheapestWithinKStops(4, f1, 0, 3, 2) == 400);
std::vector<std::vector<int>> f2 = {{0, 1, 100}, {1, 2, 100}, {0, 2, 500}};
assert(cheapestWithinKStops(3, f2, 0, 2, 1) == 200);
assert(cheapestWithinKStops(3, f2, 0, 2, 0) == 500);
assert(cheapestWithinKStops(3, {{0, 1, 5}}, 0, 2, 5) == -1);
std::cout << "layered flights OK\n";
}
function cheapestWithinKStops(n: number, flights: number[][], src: number, dst: number, k: number): number {
let cur = new Array<number>(n).fill(Infinity);
cur[src] = 0;
for (let round = 0; round <= k; round++) {
const nxt = cur.slice();
for (const [u, v, w] of flights) {
if (cur[u] !== Infinity && cur[u] + w < nxt[v]) nxt[v] = cur[u] + w;
}
cur = nxt;
}
return cur[dst] === Infinity ? -1 : cur[dst];
}
function check(ok: boolean): void {
if (!ok) throw new Error("assertion failed");
}
const f1 = [[0, 1, 100], [1, 2, 100], [2, 0, 100], [1, 3, 600], [2, 3, 200]];
check(cheapestWithinKStops(4, f1, 0, 3, 1) === 700);
check(cheapestWithinKStops(4, f1, 0, 3, 2) === 400);
const f2 = [[0, 1, 100], [1, 2, 100], [0, 2, 500]];
check(cheapestWithinKStops(3, f2, 0, 2, 1) === 200);
check(cheapestWithinKStops(3, f2, 0, 2, 0) === 500);
check(cheapestWithinKStops(3, [[0, 1, 5]], 0, 2, 5) === -1);
console.log("layered flights OK");
The layer-by-layer values for the first example (src = 0, dst = 3), computed by the code:
| After round (flights allowed) | city 0 | city 1 | city 2 | city 3 |
|---|---|---|---|---|
| 0 | 0 | ∞ | ∞ | ∞ |
| 1 | 0 | 100 | ∞ | ∞ |
| 2 | 0 | 100 | 200 | 700 |
| 3 | 0 | 100 | 200 | 400 |
With the answer is the round-2 value, 700. If you drop the copy and relax in place, a single round already produces 400 for city 3 (the relaxations chain within one pass) — a 3-flight route reported as a 1-flight answer.
Variant: an implicit graph, never stored
The lock's graph has vertices and edges, and none of them is ever materialized. neighbours is the graph. Encoding states as integers 0–9999 would let dist be a flat list instead of a dict; strings are kept here for readability.
from collections import deque
def lock_neighbours(state):
for i in range(4):
d = int(state[i])
for nd in ((d + 1) % 10, (d - 1) % 10):
yield state[:i] + str(nd) + state[i + 1:]
def open_lock(deadends, target):
dead = set(deadends)
if "0000" in dead:
return -1
dist = {"0000": 0}
q = deque(["0000"])
while q:
s = q.popleft()
if s == target:
return dist[s]
for t in lock_neighbours(s):
if t not in dist and t not in dead:
dist[t] = dist[s] + 1
q.append(t)
return -1
def explore_all():
dist = {"0000": 0}
q = deque(["0000"])
while q:
s = q.popleft()
for t in lock_neighbours(s):
if t not in dist:
dist[t] = dist[s] + 1
q.append(t)
return dist
if __name__ == "__main__":
assert open_lock(["0201", "0101", "0102", "1212", "2002"], "0202") == 6
assert open_lock(["8888"], "0009") == 1
assert open_lock(["0000"], "8888") == -1
full = explore_all()
assert len(full) == 10_000 and max(full.values()) == 20
print("implicit lock graph OK")
Variant: a product graph, (cell, keys held)
Grid cells a–f are keys, A–F the matching locks, @ the start, # walls. The state is (r, c, mask); the same cell with a different mask is a different vertex. Test grids are LeetCode 864's examples.
from collections import deque
def shortest_path_all_keys(grid):
R, C = len(grid), len(grid[0])
all_keys = 0
for r in range(R):
for c in range(C):
ch = grid[r][c]
if ch == "@":
start = (r, c)
elif "a" <= ch <= "f":
all_keys |= 1 << (ord(ch) - ord("a"))
seen = {(start[0], start[1], 0)}
q = deque([(start[0], start[1], 0, 0)])
while q:
r, c, mask, d = q.popleft()
if mask == all_keys:
return d
for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
nr, nc = r + dr, c + dc
if not (0 <= nr < R and 0 <= nc < C):
continue
ch = grid[nr][nc]
if ch == "#":
continue
if "A" <= ch <= "F" and not mask >> (ord(ch) - ord("A")) & 1:
continue # locked door, key not held
nmask = mask | (1 << (ord(ch) - ord("a"))) if "a" <= ch <= "f" else mask
if (nr, nc, nmask) not in seen:
seen.add((nr, nc, nmask))
q.append((nr, nc, nmask, d + 1))
return -1
if __name__ == "__main__":
assert shortest_path_all_keys(["@.a..", "###.#", "b.A.B"]) == 8
assert shortest_path_all_keys(["@..aA", "..B#.", "....b"]) == 6
assert shortest_path_all_keys(["@Aa"]) == -1
print("product graph OK")
Variant: estimate the state space first
A ten-line script you should write before any state search. It is the "count states" box of the pipeline diagram.
from math import factorial
def estimate(name, states, branching):
edges = states * branching
verdict = "easy" if edges <= 1e7 else "heavy" if edges <= 1e9 else "infeasible as plain BFS"
return name, states, edges, verdict
rows = [
estimate("open the lock", 10**4, 8),
estimate("8-puzzle (reachable)", factorial(9) // 2, 4),
estimate("15-puzzle (reachable)", factorial(16) // 2, 4),
estimate("keys, 30x30 grid, 6 keys", 30 * 30 * 2**6, 4),
estimate("visit all, n = 12", 12 * 2**12, 11),
]
for name, s, e, v in rows:
print(f"{name:28s} states={s:>18,} edges<={e:>20,} {v}")
assert rows[1][1] == 181_440
assert rows[2][1] == 10_461_394_944_000
assert rows[3][1] == 57_600 and rows[4][1] == 49_152
assert rows[2][3] == "infeasible as plain BFS"
Real-world uses
- Road networks and routing. Map services store road graphs with tens of millions of vertices in CSR-like arrays and model turn restrictions by making the state an edge (arriving direction) rather than an intersection — an "edge-based" or "line graph" model, a product graph in disguise. Time-dependent travel times and public transit use time-expanded or time-dependent graphs. The capstone of this module loads a real road network.
- Internet routing. BGP models autonomous systems as vertices and peering sessions as edges, with route selection constrained by policy (a valley-free path rule is effectively a product of the AS graph with a small automaton). Link-state protocols inside a network, covered on the network layer page, run Dijkstra on an explicit topology.
- Build systems and package managers. Make, Bazel, Cargo and npm model targets or packages as vertices and dependencies as directed edges, then topologically sort and detect cycles. Version resolution adds a component to the state (which version), which is why it is NP-hard in general.
- Databases. Query planners treat join orders as a search over states (sets of joined relations, a bitmask, exactly the "visit all" product graph), with dynamic programming over subsets in the classic System R design; see query planning. Graph databases store adjacency explicitly ("index-free adjacency") so traversals do not need joins.
- Garbage collectors. The heap is an implicit directed graph (objects are vertices, references are edges); marking is a traversal from the roots, never materialized as an adjacency list. See memory allocators for the allocation side.
- Compilers and verification. Control-flow graphs, call graphs and data-dependency graphs are explicit; model checkers explore the implicit product of a program's state graph with a property automaton, the same product-graph construction as the keys-and-doors problem, at a scale of billions of states with hashing tricks to fit memory.
- Sparse linear algebra and graph analytics. CSR is the standard sparse-matrix layout (SciPy's
csr_matrix, theCompressed Sparse Rowformat in numerical libraries), and graph analytics engines use the same arrays for PageRank and BFS. Search engines' link graphs are stored compressed in the same spirit (search engineering).
Pitfalls & edge cases
- Incomplete state. The classic: shortest path with "at most k" or with keys, using only the node as state. Symptom: wrong answers on some tests, often too small (an illegal path) or too large (a pruned legal path). Fix: add the missing component.
- Bloated state. Including components that never affect the future (the full path so far, a timestamp when only parity matters) multiplies the state count. Ask "do two states with different values here always have the same future?"
- Marking the start as visited too late. In implicit-graph BFS, put the start into
visitedbefore the loop, or it can be re-enqueued from a neighbour. - Dead start or target. Lock: if the start
"0000"is itself a dead-end, answer -1 before searching. Word ladder: if the end word is not in the dictionary, the answer is 0 without any search. Check these before the loop, not inside it. - Undirected edges stored once. Building an undirected adjacency list with only
adj[u].append(v)silently makes it directed. Every undirected edge must be stored twice; the handshake check (sum of degrees == 2m) catches it. - 1-indexed input. Many problems number vertices . Either allocate slots or subtract 1 on read — consistently.
- Parallel edges and self-loops. A multigraph's matrix needs counts or minimum weights, not booleans; "keep the cheapest of parallel edges" is a common requirement in shortest-path inputs. Self-loops break naive "is this a simple cycle?" logic and degree counts (a loop adds 2 to its vertex's degree).
- Matrix on a sparse graph. with a matrix is 10 GB. Read before you choose.
- Cliques from grouping. Connecting all members of a group (same bus route, same array value, same wildcard pattern) can create edges. Use a hub vertex per group, and in BFS clear a group's member list after first expanding it so it is never scanned twice.
- Layered relaxation in place. Bellman-Ford rounds for "at most k edges" must read the previous round's array. In-place updates allow more edges per round.
- Encoding collisions. Packing
(r, c, mask)into one integer as(r * C + c) << K | maskis great untilKis wrong orr * C + coverflows the shift. Assert the encoding round-trips on a few states. - Recursion on huge implicit graphs. A recursive DFS over states will overflow the stack in most languages; see DFS in depth for iterative conversion.
Variations
- Line graph (edge-based model). Vertices are the original edges; two are adjacent if one ends where the other starts. Used for turn costs and turn restrictions in road routing.
- Hypergraphs. An edge joins any number of vertices (a bus route, a group chat). Store as a bipartite graph between vertices and hyperedges — exactly the bus-routes trick.
- Condensation. Collapse each strongly connected component into one vertex to get a DAG; covered in connectivity.
- Auxiliary source and sink. Add a super-source joined to all starting points (multi-source BFS, many-to-one shortest paths) or a super-sink; flow networks rely on this (network flow).
- Vertex splitting. Replace a vertex with to put a weight or capacity on the vertex itself.
- Reverse graph. Flip every edge to answer "who can reach ?" with one traversal from ; used in Kosaraju's algorithm and in "eventual safe states".
- Complement graph. Edges where the original has none; occasionally a BFS over the complement is needed, with a "remaining unvisited set" trick to stay near .
- Dynamic graphs. Edges inserted and deleted over time; adjacency lists with hash sets, or offline tricks (process deletions in reverse as insertions with union-find).
Practice ladder
Each problem is described in my own words; follow the link for the full statement.
1. Find if Path Exists in Graph (LeetCode 1971) — Undirected edge list, is there a path between two vertices. Teaches building an adjacency list from an edge list (and storing each edge twice).
Hint
Build adj, run any traversal from the source, or use union-find on the edge list directly.
2. Find the Town Judge (LeetCode 997) — Find the person everyone trusts who trusts no one. Teaches that some graph questions need only in- and out-degrees, not a traversal.
Hint
The judge has in-degree and out-degree 0. One pass over the edges, one over the people.
Solution
def find_judge(n, trust):
score = [0] * (n + 1) # in-degree minus out-degree
for a, b in trust:
score[a] -= 1
score[b] += 1
for p in range(1, n + 1):
if score[p] == n - 1:
return p
return -1
assert find_judge(2, [[1, 2]]) == 2
assert find_judge(3, [[1, 3], [2, 3]]) == 3
assert find_judge(3, [[1, 3], [2, 3], [3, 1]]) == -1
assert find_judge(1, []) == 1
time, space. The combined score works because is reachable only with in-degree and out-degree 0.
3. Find Center of Star Graph (LeetCode 1791) — A star graph is given as edges; find the hub. Teaches reasoning about structure instead of building anything.
Hint
The centre is in every edge, so it is the vertex shared by the first two edges.
4. Keys and Rooms (LeetCode 841) — Rooms contain keys to other rooms; can you open all of them? Teaches recognizing "room → rooms whose key it holds" as a directed adjacency list given in the input.
Hint
The input already is an adjacency list. Traverse from room 0 and check that every room was visited.
5. Maximal Network Rank (LeetCode 1615) — The rank of a pair of cities is the number of roads touching either. Teaches when a matrix (or edge set) beats a list: you need "is there a road between these two?".
Hint
Rank of = . With , try all pairs with a boolean matrix.
6. Two Buttons (Codeforces 520B) — A device doubles a number or subtracts one; reach from in the fewest presses. Teaches implicit graphs on integers, bounding the state space, and the reverse-graph shortcut.
Hint
BFS works if you cap values (no optimal path needs to exceed about ). Or reason backwards from : halve when even, add one when odd, until you are at or below .
7. Minimum Genetic Mutation (LeetCode 433) — Gene strings of length 8 over ACGT, mutate one character at a time through a bank of valid genes. Teaches the word-ladder model with a tiny alphabet.
Hint
Each gene has candidate neighbours; keep the ones in the bank and BFS.
8. Snakes and Ladders (LeetCode 909) — Fewest dice rolls on a boustrophedon board with snakes and ladders. Teaches translating an awkwardly numbered board into a clean graph (square has edges to the up-to-6 squares reached by a roll, after following any snake or ladder).
Hint
Write a function from square number to (row, col) first and test it; the alternating row direction is where everyone slips. Then BFS over square numbers.
Solution
from collections import deque
def snakes_and_ladders(board):
n = len(board)
def cell(s): # square 1..n*n -> board value
q, r = divmod(s - 1, n)
row = n - 1 - q
col = r if q % 2 == 0 else n - 1 - r
return board[row][col]
dist = {1: 0}
queue = deque([1])
while queue:
s = queue.popleft()
if s == n * n:
return dist[s]
for t in range(s + 1, min(s + 6, n * n) + 1):
dest = cell(t) if cell(t) != -1 else t
if dest not in dist:
dist[dest] = dist[s] + 1
queue.append(dest)
return -1
b1 = [[-1, -1, -1, -1, -1, -1], [-1, -1, -1, -1, -1, -1], [-1, -1, -1, -1, -1, -1],
[-1, 35, -1, -1, 13, -1], [-1, -1, -1, -1, -1, -1], [-1, 15, -1, -1, -1, -1]]
assert snakes_and_ladders(b1) == 4
assert snakes_and_ladders([[-1, -1], [-1, 3]]) == 1
squares with 6 edges each: time and space.
9. Shortest Path with Alternating Colors (LeetCode 1129) — Red and blue directed edges; paths must alternate colours. Teaches the smallest product graph: state = (node, colour of the last edge).
Hint
states. Start from both (0, red) and (0, blue) at distance 0. A node's answer is the minimum over its two states.
Solution
from collections import deque
def alternating_paths(n, red_edges, blue_edges):
adj = [[[] for _ in range(n)] for _ in range(2)] # adj[colour][u]
for u, v in red_edges:
adj[0][u].append(v)
for u, v in blue_edges:
adj[1][u].append(v)
dist = [[-1] * n for _ in range(2)] # dist[last colour][node]
dist[0][0] = dist[1][0] = 0
q = deque([(0, 0), (0, 1)])
while q:
u, last = q.popleft()
nxt = 1 - last
for v in adj[nxt][u]:
if dist[nxt][v] == -1:
dist[nxt][v] = dist[last][u] + 1
q.append((v, nxt))
out = []
for v in range(n):
cands = [d for d in (dist[0][v], dist[1][v]) if d != -1]
out.append(min(cands) if cands else -1)
return out
assert alternating_paths(3, [[0, 1], [1, 2]], []) == [0, 1, -1]
assert alternating_paths(3, [[0, 1]], [[2, 1]]) == [0, 1, -1]
assert alternating_paths(3, [[0, 1]], [[1, 2]]) == [0, 1, 2]
on a graph of states.
10. Cheapest Flights Within K Stops (LeetCode 787) — The layered-graph problem worked through above. Teaches why the state must include the number of flights used.
Hint
rounds of Bellman-Ford, each reading only the previous round's array. Or Dijkstra over (city, stops).
11. Bus Routes (LeetCode 815) — Fewest buses between two stops. Teaches the bipartite (stops vs routes) model, which avoids building quadratic cliques.
Hint
BFS over routes, not stops: from a stop, enter every route serving it; from a route, reach every stop on it. Mark routes as used so each route's stop list is scanned once.
Solution
from collections import deque, defaultdict
def num_buses(routes, source, target):
if source == target:
return 0
routes_at = defaultdict(list) # stop -> routes (the bipartite edges)
for r, stops in enumerate(routes):
for s in stops:
routes_at[s].append(r)
used_route = [False] * len(routes)
seen_stop = {source}
q = deque([(source, 0)])
while q:
stop, buses = q.popleft()
for r in routes_at[stop]:
if used_route[r]:
continue
used_route[r] = True
for s in routes[r]:
if s == target:
return buses + 1
if s not in seen_stop:
seen_stop.add(s)
q.append((s, buses + 1))
return -1
assert num_buses([[1, 2, 7], [3, 6, 7]], 1, 6) == 2
assert num_buses([[7, 12], [4, 5, 15], [6], [15, 19], [9, 12, 13]], 15, 12) == -1
assert num_buses([[1, 2]], 1, 1) == 0
Each route's stop list is scanned at most once: time and space.
12. Jump Game IV (LeetCode 1345) — From index jump to or to any index with the same value. Teaches the clique blow-up (all-equal arrays give edges) and the "clear the group after first use" fix.
Hint
Group indices by value. When you first expand any index of a value, enqueue the whole group and then empty it; later visitors of that value find nothing to scan.
Solution
from collections import deque, defaultdict
def min_jumps(arr):
n = len(arr)
groups = defaultdict(list)
for i, x in enumerate(arr):
groups[x].append(i)
dist = [-1] * n
dist[0] = 0
q = deque([0])
while q:
i = q.popleft()
if i == n - 1:
return dist[i]
nbrs = groups.pop(arr[i], []) # clique edges, used once
nbrs.extend((i - 1, i + 1))
for j in nbrs:
if 0 <= j < n and dist[j] == -1:
dist[j] = dist[i] + 1
q.append(j)
return -1
assert min_jumps([100, -23, -23, 404, 100, 23, 23, 23, 3, 404]) == 3
assert min_jumps([7]) == 0
assert min_jumps([7, 6, 9, 6, 9, 6, 9, 7]) == 1
assert min_jumps([1] * 50_000) == 1
: every index is enqueued once and every group is scanned once.
13. Shortest Path in a Grid with Obstacles Elimination (LeetCode 1293) — Walk a grid, may knock down up to walls. Teaches the layered product state (r, c, removals left) and pruning with dominance.
Hint
State (r, c, left). Prune: if , the Manhattan path is always possible. Also keep, per cell, the best left seen so far and skip states that are dominated.
14. Shortest Path Visiting All Nodes (LeetCode 847) — Shortest walk (revisits allowed) that touches every node, . Teaches the (node, visited mask) product graph and multi-source starts.
Hint
states. Start BFS from every (v, 1 << v) at distance 0. The first state with a full mask gives the answer.
15. Flight Discount (CSES 1195) — Cheapest route when one flight may be taken at half price. Teaches the two-layer graph (coupon unused / used) combined with Dijkstra.
Hint
State (city, used). From layer 0, each flight goes to layer 0 at full price or to layer 1 at half price; from layer 1 only full price. Answer: distance to (n, 1) (or the minimum of both layers). Use 64-bit costs.
Common mistakes & interview follow-ups
"Why BFS and not DFS for the lock?" BFS explores in order of distance, so the first time it reaches the target is a shortest path. DFS finds a path, not the shortest, unless you search exhaustively.
"How big is your state space?" Always have the number ready. Interviewers ask it to check you understand the cost before you code. For the lock: states, edges.
"Can you avoid building the graph?" Yes — generate neighbours on demand. Only build an explicit adjacency list when neighbour generation is expensive or the graph is reused for many queries.
"What if the dictionary has a million words?" Wildcard-pattern buckets or per-position hashing; precompute neighbour lists once if there are many queries; bidirectional BFS to shrink the explored region (BFS in depth quantifies the saving).
"What if k is huge?" For layered graphs, beyond stops is irrelevant (a cheapest walk with more stops would repeat a city, and with non-negative prices that never helps), so cap it.
"What if the graph does not fit in memory?" Compress (CSR, delta-encoded neighbour ids), partition, or stream the edge list; external-memory BFS processes a layer at a time from disk. For implicit graphs, trade memory for time with iterative deepening (no visited set), covered in DFS in depth.
"Adjacency list or matrix?" Answer with the numbers: , , the dominant operation. Sparse plus traversal means list or CSR; small dense plus edge queries means matrix.
Mistakes interviewers watch for: forgetting the second direction for undirected edges; a state missing a component; computing neighbours that include walls or dead-ends; enqueuing the same state many times because visited is set on dequeue instead of enqueue.
Quick quiz
1. A 2×3 sliding puzzle has 720 tile arrangements. Why does BFS from the solved state find only 360?
Answer
Every legal move preserves a parity invariant of the permutation (combined with the blank's position), so the arrangements split into two classes of 360 that cannot reach each other. The 3×3 puzzle shows the same halving: arrangements, reachable.
2. You must find the cheapest route using at most 3 discount coupons on a graph with cities and roads. How many states and edges does the product graph have?
Answer
State (city, coupons used) with 4 values: states. Each road gives a full-price edge in each of the 4 layers and a discounted edge in each of the first 3: directed edges per direction of travel. Dijkstra on that is instant.
3. Which representation would you use for (a) , , many BFS runs; (b) , Floyd-Warshall; (c) Kruskal's MST?
Answer
(a) CSR (or adjacency lists): sparse, traversal-heavy, static. (b) Adjacency matrix: Floyd-Warshall is defined on it and cells is tiny. (c) Edge list, sorted by weight.
4. In the cheapest-flights layered algorithm, what goes wrong if you update the distance array in place within a round?
Answer
A relaxation can read a value that was already improved in the same round, so one round can chain several flights. The result may use more than flights; in the worked example a single in-place round reports 400 for a destination that needs 3 flights.
5. Why is "state = current cell" wrong for the keys-and-doors grid?
Answer
Two arrivals at the same cell with different key sets have different futures (one can pass a door, the other cannot), so the state violates the Markov property. Marking the cell visited after the first arrival can prune the only valid route. The state must be (cell, key mask).
Further reading / sources
- Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein, Introduction to Algorithms, 4th ed., chapter 20 "Elementary Graph Algorithms" (§20.1 representations).
- Steven S. Skiena, The Algorithm Design Manual, 3rd ed., chapter 7 "Graph Traversal" and §8 "Weighted Graph Algorithms"; the "war stories" are the best collection of real modeling decisions in print.
- Robert Sedgewick and Kevin Wayne, Algorithms, 4th ed., §4.1–4.2 (undirected and directed graph APIs, symbol graphs that map names to vertex ids).
- Stuart Russell and Peter Norvig, Artificial Intelligence: A Modern Approach, 4th ed., chapter 3 "Solving Problems by Searching" (state spaces, branching factor, sliding-tile puzzles).
- Antti Laaksonen, Competitive Programmer's Handbook, chapter 11 "Basics of graphs" (representations) and chapter 12.
- Richard E. Korf, "Depth-first iterative-deepening: An optimal admissible tree search", Artificial Intelligence 27(1), 1985 — the 15-puzzle experiments that show why plain BFS is out of the question there.
- Daniel Delling, Peter Sanders, Dominik Schultes, Dorothea Wagner, "Engineering Route Planning Algorithms", in Algorithmics of Large and Complex Networks, LNCS 5515, 2009 — road graph models, turn costs, time-expanded transit graphs.
- cp-algorithms: Breadth-first search (applications section lists several product-graph tricks).
- Leonhard Euler, "Solutio problematis ad geometriam situs pertinentis" (1736); Seven Bridges of Königsberg on Wikipedia for the history.
Previous lesson: Graphs (overview) · Next lesson: BFS in Depth
Related: Matrices & 2D Grids · Queues, Deques & Circular Buffers · Hash Tables · DFS in Depth · Shortest Paths · Bit Manipulation · Dynamic Programming · Course home