Representing a graph
Pick between an adjacency list, a matrix and an implicit grid by the two operations you actually run, and do the arithmetic that settles it.
A graph is a set of nodes and a set of edges between them. Every storage decision comes down to two operations you will run thousands of times: give me the neighbours of u, and is there an edge from u to v. The two standard representations make one of those cheap and the other expensive, and the third option stores nothing at all.
The adjacency list
One list per node, holding that node's neighbours. Built from an edge list in a single pass:
from collections import defaultdict
def build(edges, directed=False):
graph = defaultdict(list)
for u, v in edges:
graph[u].append(v)
if not directed:
graph[v].append(u)
return graph
Space is V + 2E slots for an undirected graph: one bucket per node, one entry per endpoint of every edge. That is O(V + E). Iterating the neighbours of u costs O(deg(u)), and iterating every neighbour of every node costs O(V + E) total, because the sum of all degrees is 2E. Testing whether a specific edge exists means scanning a bucket — O(deg(u)).
The adjacency matrix
A V by V table where cell (u, v) says whether the edge is there.
adj = [[0] * n for _ in range(n)]
for u, v in edges:
adj[u][v] = 1
adj[v][u] = 1 # drop this line for a directed graph
Space is V² cells no matter how many edges exist. The edge test is one index — O(1). Getting the neighbours of u costs O(V), because you scan the whole row including the V − deg(u) zeros.
| Adjacency list | Adjacency matrix | |
|---|---|---|
| Space | O(V + E) | O(V²) |
| Neighbours of u | O(deg(u)) | O(V) |
| Is u–v an edge? | O(deg(u)) | O(1) |
| Add an edge | O(1) | O(1) |
| Full traversal | O(V + E) | O(V²) |
Where the matrix wins
Counting slots, the two tie when V + 2E = V², which is E ≈ V²/2 — essentially a complete graph. Counting bytes the matrix pulls ahead earlier, because a flat row of bytes has no per-entry object overhead. So the real trigger is a pair of conditions, not a single threshold: the graph is dense, and V is small enough that V² fits.
Run the numbers at V = 1,000. A sparse graph with E = 3,000 edges needs 1,000 + 6,000 = 7,000 list entries against 1,000,000 matrix cells — 140 times the memory to store mostly zeros. A dense graph with E = 400,000 out of the 499,500 possible needs 1,000 + 800,000 = 801,000 list entries against the same 1,000,000 cells, and the matrix answers the edge test in one index instead of an 800-long scan (the average degree is 2E/V = 800). The matrix wins the second case and loses the first badly.
There is also a hard ceiling. At V = 5,000 the matrix is 25 million cells, about 25 MB at one byte each — workable. At V = 10⁵ it is 10¹⁰ cells; even one bit per cell is 1.25 GB, so the matrix is not an option at that size whatever the density. And a full traversal of a matrix is O(V²) = 10¹⁰ steps, which at roughly 10⁸ simple operations per second is about 100 seconds — the same wall described in complexity by counting. Default to the list; reach for the matrix only when you can name why.
Directed, undirected, weighted
Undirected means both append lines. Writing only one of them is the most
common bug in this module and it hides well: a traversal from one end reaches
everything, so half the tests pass.
Directed means one line, and it means indegree starts to matter — the peeling algorithm in cycles and topological order is built entirely on it.
Weighted means the neighbour entry carries a number: graph[u].append((v, w))
in a list, or adj[u][v] = w in a matrix. In the matrix case initialise the
empty cells to math.inf, not 0. A zero means "free edge", and an
all-pairs pass will happily route every path through edges that do not exist.
The implicit graph
Most grid problems are graph problems where nobody builds the graph. The nodes are the cells and the neighbours are computed:
DIRS = ((1, 0), (-1, 0), (0, 1), (0, -1))
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]) and grid[nr][nc] != '#':
yield nr, nc
A 1,000 × 1,000 grid is V = 10⁶ nodes and just under 2 × 10⁶ undirected edges.
An explicit adjacency list would hold about 4 million entries to store what four
(dr, dc) pairs compute in constant time — so build nothing, and let the
traversal call neighbours. The traversal itself is O(V + E) ≈ 3 × 10⁶ steps,
comfortably inside a second.
The same trick covers graphs whose nodes are states rather than places: word ladders where the neighbours are the one-letter edits, or puzzle boards where the neighbours are the legal moves. If you can write a function from a node to its neighbours, you have a graph, and every algorithm in this module runs on it unchanged.
In an interview
State the representation and its cost before writing a line: "adjacency list, O(V + E) space; V is 10⁵ here so a matrix would be 10¹⁰ cells and is not an option." That single sentence shows you sized the input, which is what the question is testing — the same move as step 1 of the solving loop.
The mistake that loses points: materialising an adjacency list for a grid. It costs a screen of code, several million entries, and buys nothing over four offsets. The interviewer reads it as pattern-matching on "graph problem" instead of thinking about the input in front of you.
Check yourself
V = 2,000 nodes, E = 1,900,000 edges, and the hot operation is "is u adjacent to v". Which representation, and why?
The graph is nearly complete: 1.9 million of the 1,999,000 possible undirected edges. The matrix costs V² = 4,000,000 cells — about 4 MB at one byte each — and answers the query with one index. The list would scan a neighbour bucket averaging 2E/V = 1,900 entries. Take the matrix.
You build an undirected graph and only append v to graph[u]. What breaks,
and when do you notice?
Every edge becomes one-way. A traversal starting from one endpoint reaches everything; starting from the other it stops immediately. Roughly half your examples still pass, which is exactly why this bug survives your own testing.
A 1,000 × 1,000 grid with four-directional movement. How many nodes and edges, and what does that say about building an adjacency list?
10⁶ nodes, and just under 2 × 10⁶ undirected edges — each interior cell has four, and each edge is shared by two cells. The list would hold about 4 million entries to replace a four-element tuple of offsets. Compute the neighbours instead.