Graph Representations

A graph G = (V, E) can be stored in several distinct data structures, each making different operations cheap and others expensive. The three classical representations are: adjacency list (each vertex maps to a list of its neighbors — Θ(V + E) space, fastest neighbor iteration), adjacency matrix (a V × V boolean/weight matrix — Θ(V²) space, O(1) edge lookup), and edge list (a flat list of (u, v[, w]) triples — Θ(E) space, no fast neighbor lookup). The right choice depends on graph density (sparse vs dense), the operation mix (do you iterate neighbors or test edge existence?), and the algorithm you’ll run (most graph algorithms — BFS, DFS, Dijkstra, Kruskal — assume adjacency list and degrade if forced to use a matrix). Specialized representations (compressed sparse row, implicit graphs, weighted-edge structs, incidence matrices) extend the family for niche use cases. Picking the right representation can change an algorithm from O(V + E) to O(V²) for the same logical operation — a large difference for sparse graphs.

1. Intuition — Three Ways to Describe a Friend Network

Suppose you want to record who’s friends with whom in a group of 1000 people. Three natural data layouts:

• Per-person address book (adjacency list): for each person, list everyone they’re friends with. If you have on average 50 friends each, you store 1000 short lists totaling ~50 000 entries. Looking up “who are Alice’s friends?” is one dictionary lookup. Looking up “is Alice friends with Bob?” requires scanning Alice’s list — typically fast but proportional to her friend count.

• Big spreadsheet (adjacency matrix): a 1000×1000 grid where cell (i, j) is 1 if person i is friends with j, else 0. Cell lookup (Alice, Bob) is a single array access — fastest possible. But the spreadsheet is mostly zeros (sparse friendship graph), and it costs 1 000 000 bits regardless of how few friendships exist.

• Master friendship list (edge list): a single list of (Alice, Bob), (Alice, Carol), (Bob, David), .... Compact (only as many entries as friendships). But “who are Alice’s friends?” requires scanning the entire list — terrible if you ask that question often.

The trade-off is time vs space vs which operation you optimize for. Most graph algorithms iterate over neighbors more than they test specific-pair adjacency, so adjacency lists win the default vote. But for dense graphs, or for algorithms like Floyd-Warshall that fundamentally need an O(V²) matrix anyway, the matrix is the right call. Edge lists are niche but useful for input parsing and for Kruskal’s MST (which sorts edges and processes them one at a time).

2. Definitions and Notation

Let n = |V| (number of vertices) and m = |E| (number of edges).

• Sparse graph: m = O(n) or m = O(n log n). Examples: road networks, social networks, web graphs, most “real-world” graphs.
• Dense graph: m = Θ(n²). Examples: complete graphs, all-pairs interaction matrices.

The boundary between sparse and dense determines which representation is asymptotically better. The default assumption in algorithm analysis is sparse, which is why adjacency lists dominate textbooks.

3. Adjacency List

3.1 Definition

For each vertex u, store a list (or set) of its neighbors. In Python:

graph: dict[int, list[int]] = {
    0: [1, 2],
    1: [0, 3],
    2: [0, 3],
    3: [1, 2],
}

For undirected graphs, each edge appears in two lists (once for each endpoint). For directed graphs, the edge (u, v) appears only in graph[u].

For weighted graphs, store (neighbor, weight) tuples:

graph: dict[int, list[tuple[int, float]]] = {
    0: [(1, 5.0), (2, 3.5)],
    1: [(0, 5.0), (3, 2.0)],
    ...
}

3.2 Space

Θ(V + E). The + V is for vertices that may have no edges (still need a key in the dictionary). The + E is 2E for undirected (each edge stored twice) or E for directed.

For sparse graphs with m = O(n), this is O(n) total — vastly less than the matrix’s O(n²).

3.3 Time per Operation

Operation	Cost	Notes
Iterate neighbors of u	O(deg(u))	Optimal — must enumerate them anyway
Test “is (u, v) an edge?”	O(deg(u))	Linear scan of graph[u]
Add edge (u, v)	O(1)	Append to list (list.append)
Remove edge (u, v)	O(deg(u))	Linear scan + remove
Iterate all edges	O(V + E)	Outer loop over vertices, inner over their lists

The “test edge existence” cost can be reduced from O(deg(u)) to O(1) expected by replacing each list with a hash set — but at the cost of memory overhead and slower iteration. For most algorithms (which iterate, not lookup), the list form wins.

3.4 When to Use

Default choice for sparse graphs. All of BFS, DFS, Dijkstra, Bellman-Ford, Topological Sort, Kruskal, Prim, Tarjan SCC, Tarjan bridges, and Bipartite Check are designed assuming adjacency-list input.

If a problem mentions “graph with V vertices and E edges” without claiming density, default to adjacency list.

3.5 Variants

• Dictionary of lists (Python idiomatic, dynamic).
• Array of lists (faster if vertices are integers 0..n-1).
• Linked-list per vertex (textbook classical; rarely faster than dynamic arrays in modern languages).
• Sorted lists (enable binary-search edge lookup in O(log deg(u))); rarely worth the maintenance cost.
• Adjacency dict-of-dicts (graph[u][v] = weight): fast edge-existence and weight lookup, slightly higher constant.

4. Adjacency Matrix

4.1 Definition

A V × V 2D array A where A[u][v] = 1 if there is an edge from u to v, else 0. For weighted graphs, store the weight: A[u][v] = w(u, v) if edge exists, else ∞ (or 0 if 0 doesn’t have a weighted meaning in your problem — be careful).

INF = float('inf')
matrix = [
    [0,   5,   3,   INF],
    [5,   0,   INF, 2],
    [3,   INF, 0,   1],
    [INF, 2,   1,   0],
]

For undirected graphs, the matrix is symmetric: A[u][v] == A[v][u]. For directed graphs, asymmetric.

4.2 Space

Θ(V²). Independent of E. Even an empty graph (no edges) on n vertices costs n² cells.

For sparse graphs (m = O(n)), the matrix is n²/n = n times larger than the adjacency list. For n = 10^4, that’s 10^8 cells (maybe 400 MB at 4 bytes each) vs 10^4 entries — wildly wasteful. For n = 10^5, the matrix doesn’t fit in memory.

4.3 Time per Operation

Operation	Cost	Notes
Iterate neighbors of u	O(V)	Must scan a full row, including non-edges
Test “is (u, v) an edge?”	O(1)	Single array access — best possible
Add edge (u, v)	O(1)	Single array assignment
Remove edge (u, v)	O(1)	Single array assignment
Iterate all edges	O(V²)	Must scan entire matrix

The asymmetry matters: adjacency matrix wins on edge lookup, loses on neighbor iteration. Algorithms that do many edge-existence tests (Floyd-Warshall, transitive closure, some all-pairs problems) prefer the matrix; algorithms that iterate neighbors (BFS, DFS, Dijkstra) prefer adjacency lists.

4.4 When to Use

• Dense graphs where m = Θ(n²). Storage is the same O(n²) either way; matrix’s O(1) edge lookup is then a free bonus.
• Algorithms that need O(1) edge-existence tests: Floyd-Warshall (all-pairs shortest path), transitive closure, matrix-multiplication-based BFS.
• Small graphs (n ≤ 1000 or so) where n² is tractable and the simplicity is worth it.
• Graph products and tensor algebra (sometimes you literally want to multiply matrices).

4.5 Variants

• Bit-matrix (one bit per cell instead of one int): cuts space by 32× or 64×. Useful for very large n with boolean adjacency.
• Compressed bit-matrix (storing only the upper triangle for undirected): cuts space by 2×. Saves memory but complicates indexing.
• Sparse-matrix formats (CSR, CSC): see §6 — these are essentially adjacency lists in disguise.

5. Edge List

5.1 Definition

A flat list of all edges, each represented as (u, v) (or (u, v, w) for weighted graphs):

edges: list[tuple[int, int, float]] = [
    (0, 1, 5.0),
    (0, 2, 3.5),
    (1, 3, 2.0),
    (2, 3, 1.0),
]

For undirected graphs, store each edge once (not twice — undirected edge list omits the duplicates).

5.2 Space

Θ(E). No per-vertex overhead.

5.3 Time per Operation

Operation	Cost	Notes
Iterate neighbors of u	O(E)	Scan whole list filtering by u — terrible
Test “is (u, v) an edge?”	O(E)	Linear scan
Add edge (u, v)	O(1)	Append
Remove edge (u, v)	O(E)	Linear scan
Iterate all edges	O(E)	Optimal

Edge list is bad for any operation indexed by vertex. It’s only good for “iterate all edges in some order” — which is exactly what some algorithms want.

5.4 When to Use

• Kruskal’s MST sorts all edges by weight, then processes them in order. Edge list is the natural input format.
• Bellman-Ford relaxes each edge V - 1 times; does not need vertex-indexed neighbor lookup; edge list works.
• Input parsing: most graph problems’ input is given as an edge list (m lines, each u v or u v w); convert to adjacency list as a preprocessing step unless the algorithm doesn’t need it.
• Very space-constrained scenarios with small m and you only need to iterate.

5.5 Conversion

Building an adjacency list from an edge list takes O(V + E):

def to_adjacency_list(edges: list[tuple[int, int]], n: int) -> dict[int, list[int]]:
    graph: dict[int, list[int]] = {i: [] for i in range(n)}
    for u, v in edges:
        graph[u].append(v)
        graph[v].append(u)              # undirected; omit for directed
    return graph

If your algorithm needs vertex-indexed access at all, do this conversion once up front.

6. Compressed Sparse Row (CSR) — The Performance Variant

For very large sparse graphs (millions of vertices/edges) where cache-friendliness matters, the Compressed Sparse Row representation is standard in scientific-computing libraries (NetworkX’s “fast” mode, GraphBLAS, igraph, scipy.sparse).

CSR uses two arrays:

• indptr of length n + 1: indptr[u] is the starting index in indices of vertex u’s neighbors.
• indices of length m (or 2m for undirected): the flat concatenation of every vertex’s neighbor list, in vertex order.

To get the neighbors of u: indices[indptr[u] : indptr[u+1]].

6.1 Why It’s Faster Than Dict-of-Lists

• Cache locality: the entire neighbor list is contiguous in memory. Modern CPUs love sequential access.
• No object overhead: each Python list has ~56 bytes overhead per object; CSR has zero per-vertex overhead beyond two integer arrays.
• Vectorizable: numpy operations (e.g., indices[indptr[u]:indptr[u+1]]) are C-speed array slicing, not Python iteration.

6.2 Trade-Off

CSR is read-optimized, not write-optimized. Adding an edge requires shifting indices and updating indptr — O(V + E) per insertion. Use CSR when the graph is built once and queried many times.

6.3 Variants

• CSC (Compressed Sparse Column): the transpose of CSR. Stores in-edges instead of out-edges. Useful for directed graph algorithms that iterate predecessors.

7. Implicit and On-the-Fly Graphs

Some graphs are never materialized:

• Grid graphs: “Each cell is a vertex; neighbors are the 4 (or 8) adjacent cells.” No need to store edges; compute neighbors as (r ± 1, c) and (r, c ± 1) on demand. Space: just the grid itself.
• Game-state graphs: vertices are board positions; edges are legal moves. Generated by the move-generation function. Storing the entire graph is infeasible (combinatorial explosion); on-the-fly generation is mandatory.
• Web graphs: crawling generates edges as you visit pages. The graph is too big to fit anywhere.

For implicit graphs, “representation choice” reduces to “what data structure do you maintain for the visited set and the frontier” — typically a hash set and a queue/stack.

8. Comparison Table — All Together

Representation	Space	Iterate neighbors of u	Test edge (u, v)	Iterate all edges	Best for
Adjacency list	O(V + E)	O(deg(u))	O(deg(u))	O(V + E)	Sparse graphs, BFS/DFS/Dijkstra/Kruskal/Prim
Adjacency matrix	O(V²)	O(V)	O(1)	O(V²)	Dense graphs, Floyd-Warshall, transitive closure
Edge list	O(E)	O(E)	O(E)	O(E)	Kruskal input, Bellman-Ford, parsing
CSR	O(V + E)	O(deg(u)) (cache-fast)	O(deg(u)) (binary-search if sorted: O(log deg(u)))	O(V + E)	Massive static sparse graphs
Implicit	O(1) (graph) + O(V) (state)	O(neighbor-gen cost)	depends	O(V + E)	Grids, game trees, web crawls

The single most important question for the choice: is your graph sparse or dense? That determines whether to default to adjacency list (sparse) or matrix (dense). The second question: what operations dominate? Matrix wins on edge lookup; lists win on neighbor iteration.

9. Memory Math — Why Density Matters

Concrete example: a graph with n = 10⁴ vertices.

m (edges)	List space	Matrix space	List vs matrix
10⁴ (sparse)	~80 KB	~400 MB	matrix is 5000× larger
10⁵	~800 KB	~400 MB	matrix is 500× larger
10⁶	~8 MB	~400 MB	matrix is 50× larger
10⁷ (dense)	~80 MB	~400 MB	matrix is 5× larger
10⁸ (≈ n²)	~800 MB	~400 MB	matrix is smaller

Where:

• List space: ~8(V + 2E) bytes (8 bytes per int, edges stored twice for undirected).
• Matrix space: 4 · V² bytes (4 bytes per int cell).

For sparse graphs, the matrix wastes orders of magnitude of memory storing zeros. For truly dense graphs (close to n² edges), the list overhead (Python list per vertex + tuple per edge) catches up to the matrix’s flat layout.

The crossover point in pure space is around m ≈ V²/2 — i.e., when the graph is half-complete. In practice, the list is preferred until m is much closer to V² because list operations are also asymptotically faster for typical algorithms.

10. Algorithm Complexity Depends on Representation

Same algorithm, different data structures, different complexities:

Algorithm	With adjacency list	With adjacency matrix
BFS / DFS	O(V + E)	O(V²) (must scan each row)
Dijkstra (binary heap)	O((V + E) log V)	O(V² log V) (heap version) or O(V²) (array-based)
Prim (binary heap)	O((V + E) log V)	O(V²) (array-based, simpler for dense graphs)
Kruskal	O(E log E) (needs edge list, not adj list per se)	n/a
Bellman-Ford	O(V·E)	O(V³)
Floyd-Warshall	n/a	O(V³) (matrix is required)
Transitive closure	O(V·E)	O(V³) (or O(V^ω) via fast matrix mult)

For BFS on a dense graph (E ≈ V²), adjacency list and matrix are both O(V²). For BFS on a sparse graph (E ≈ V), adjacency list is O(V) while matrix is still O(V²) — a quadratic blowup just from picking the wrong representation.

This is the whole reason representation choice matters in interviews: getting it wrong silently degrades your algorithm by a factor of V/(deg) for sparse inputs.

11. Tiny Worked Example — Same Graph, Three Forms

Vertices 0..3. Undirected edges: (0,1), (0,2), (1,3), (2,3).

Adjacency list:

{0: [1, 2], 1: [0, 3], 2: [0, 3], 3: [1, 2]}

Space: 4 dict entries + 8 list entries (each edge stored twice) = ~12 ints + Python overhead.

Adjacency matrix:

   0  1  2  3
0 [0  1  1  0]
1 [1  0  0  1]
2 [1  0  0  1]
3 [0  1  1  0]

Space: 16 cells = 16 ints + 2D-array overhead.

Edge list:

[(0, 1), (0, 2), (1, 3), (2, 3)]

Space: 4 tuples × 2 ints = 8 ints + tuple/list overhead.

Operations on this 4-vertex example all take similar time, but observe the asymptotic divergence: at n = 10⁴ with the same edge density, edge list is ~80 KB, list is ~80 KB, matrix is ~400 MB.

12. Diagram — The Three Representations

flowchart LR
  subgraph "Adjacency list"
    AL0[0 → 1, 2]
    AL1[1 → 0, 3]
    AL2[2 → 0, 3]
    AL3[3 → 1, 2]
  end
  subgraph "Adjacency matrix (4×4)"
    AM["[[0,1,1,0],<br/>[1,0,0,1],<br/>[1,0,0,1],<br/>[0,1,1,0]]"]
  end
  subgraph "Edge list"
    EL["[(0,1), (0,2),<br/>(1,3), (2,3)]"]
  end

What this diagram shows. Three side-by-side renderings of the same 4-vertex graph from §11. The adjacency list (left) maps each vertex to its neighbor list — compact, efficient for traversal, the default for sparse graphs. The adjacency matrix (center) is a 2D grid where row u column v indicates an edge — wastes space on zeros for sparse graphs but offers O(1) edge-existence checks. The edge list (right) is a flat sequence of edges with no per-vertex indexing — useful when the algorithm processes edges in a specific order (e.g., sorted by weight in Kruskal’s MST). The same logical graph, three storage strategies, three different cost profiles for the operations you’ll perform on it.

13. Choosing in Practice — A Decision Flowchart in Prose

Ask in order:

1. Is the graph implicit (grid, game tree, web)? Use on-the-fly neighbor generation; representation question is moot.
2. Is the graph dense (m ≈ n²)? Adjacency matrix.
3. Does the algorithm fundamentally need O(1) edge tests (Floyd-Warshall, transitive closure)? Adjacency matrix.
4. Does the algorithm process edges in a global order (Kruskal sort-by-weight)? Edge list (often built from input directly).
5. Otherwise (sparse graph, BFS/DFS/Dijkstra/Bellman-Ford/Prim/Tarjan/etc.)? Adjacency list. Default.
6. Is the graph huge (millions of vertices) and read-mostly? CSR.
7. Need fast edge-existence test and fast neighbor iteration? Adjacency dict-of-sets (graph[u]: set[int]).

If your interviewer doesn’t specify, ask: “How dense is the graph? What operations dominate?” Then state your choice with the reasoning.

14. Common Interview Problems Where Representation Matters

Problem	Representation question
LC 207 — Course Schedule	Build adj list from edge list
LC 743 — Network Delay Time	Adj list for Dijkstra
LC 547 — Number of Provinces	Input is matrix; convert to adj list or process directly
LC 261 — Graph Valid Tree	Edge list → adj list, then DFS
LC 1334 — Find the City With the Smallest Number of Reachable Neighbors	Floyd-Warshall → matrix
LC 1631 — Path With Minimum Effort	Implicit grid graph; on-the-fly neighbors
Classic — “Read m edges, compute MST”	Edge list → Kruskal directly
Classic — “All-pairs shortest path on dense graph”	Matrix → Floyd-Warshall

If the input is given as a matrix but the algorithm wants an adjacency list, convert in O(n²) first. If you’re handed an adjacency list and need the matrix, convert in O(n + m).

15. Pitfalls

15.1 Defaulting to Matrix on a Sparse Graph

A 10⁵-vertex sparse graph allocated as a matrix is ~40 GB. The naive choice silently kills your program with MemoryError (or slow disk swap). Always check density before choosing the matrix.

15.2 Defaulting to Matrix Out of Habit (Dense Default)

Some textbooks and intro courses (especially older ones) lead with the matrix as the “definitional” representation. In practice, sparse graphs dominate real-world data; default to adjacency list.

15.3 Storing Undirected Edges Only Once in Adjacency List

For an undirected edge (u, v), you must add v to graph[u] and u to graph[v]. Forgetting one direction makes BFS/DFS asymmetric — you visit v from u but not vice versa. Common bug; spot it by testing connectivity from a few different starts.

15.4 Storing Undirected Edges Twice in Edge List

The opposite mistake: edge list for undirected graphs stores each edge once, not twice. Double-counting confuses Kruskal (each edge processed twice, may form spurious cycles) and inflates m.

15.5 Using 0 as “No Edge” in a Weighted Matrix

If your weights can be 0, you can’t use 0 as the no-edge sentinel — 0 and “no edge” become indistinguishable. Use ∞ (float('inf') in Python) or a separate boolean adjacency matrix alongside the weight matrix.

15.6 Implicit Graphs Without a Visited Set

The “neighbors are computed on-the-fly” pattern (grids, game trees) doesn’t relieve you of needing a visited set — you’ll loop forever otherwise. The visited set is the representation in implicit cases; track it carefully.

15.7 Mutating Adjacency List During Iteration

Standard Python footgun: for v in graph[u]: graph[u].remove(v) raises RuntimeError. Iterate over a copy or build a new list.

15.8 Off-by-One in Vertex Numbering

If your input is 1-indexed but you allocate arrays of size n (0-indexed), array graph[n] is out of bounds. Either normalize at input boundary or allocate n + 1 slots and accept the wasted slot 0.

15.9 Adjacency List With Duplicate Edges Not Deduplicated

If the input has (0, 1) twice (e.g., from a multigraph or careless data), the adjacency list ends up with graph[0] = [1, 1]. Most algorithms treat this as a “multi-edge” (run twice), which may or may not be the intent. Decide and dedupe at input time if needed.

15.10 Confusing Directed and Undirected Storage

Directed adjacency list: edge (u, v) lives only in graph[u]. Undirected: lives in both graph[u] and graph[v]. Mixing the conventions silently breaks every algorithm. State it explicitly when you build the structure.

16. Open Questions

• What’s the most cache-efficient layout for graphs that don’t fit in cache? Active research area; CSR is standard but research on novel layouts (Hilbert-curve ordering, random-walk-aware layout) is ongoing. Verify state of the art.
• When does O(V^ω) matrix-multiplication-based BFS (Yuster-Zwick) beat ordinary BFS in practice? Mostly theoretical; the constants are too large for real-world use.

17. See Also

• Breadth-First Search — assumes adjacency-list input
• Depth-First Search — same
• Dijkstra’s Algorithm — adjacency list + priority queue
• Bellman-Ford — works naturally on edge list
• Floyd-Warshall — adjacency matrix is essentially required
• Kruskal’s Algorithm — sorts edge list, uses Union-Find
• Prim’s Algorithm — adjacency list with priority queue, or matrix for dense graphs
• Connected Components — algorithm choice depends on representation
• Strongly Connected Components — adjacency list is standard input
• Union-Find — independent of graph representation; complements all of them
• Big-O Notation
• SWE Interview Preparation MOC