Data structures · intermediate
Graph representation
A graph represents vertices and edges using a structure such as an adjacency list, adjacency matrix, or edge list, each exposing different storage and query costs.
Why it matters
The representation can dominate a graph algorithm's memory use and neighbor-enumeration cost, especially when choosing between sparse and dense graphs.
Mental model
How to reason about graph representation
An adjacency list stores only outgoing neighbors; a matrix reserves a cell for every possible vertex pair; an edge list stores relationships as records without direct neighbor indexing.
Analogy
A city can keep, for each intersection, a list of connecting roads; maintain a giant yes/no grid for every pair; or keep one master ledger of roads. Each answers different questions cheaply.
Examples
See the boundary, not just the happy path
Worked example · Sparse graph
A: [B, D]
B: [C]
C: []
D: [C]This adjacency list uses O(V + E) storage and enumerates A's outgoing neighbors in time proportional to A's degree.
Worked example · Constant-time edge test
matrix[u][v] != 0An adjacency matrix tests a particular edge in O(1), at the cost of Theta(V^2) cells even when few edges exist.
Useful contrast · Directed versus undirected
directed u -> v; undirected stores u-v in both adjacency listsRepresentation must preserve direction semantics; adding only one list entry for an undirected edge makes traversal asymmetric.
Common mistakes
Misconceptions to remove early
Choosing a matrix by default
For a sparse graph, Theta(V^2) storage can dwarf the actual edge set. Choose it when density or constant-time edge tests justify that cost.
Forgetting parallel edges or weights
A Boolean matrix or neighbor set can collapse multiple edges and omit metadata. Match the element type to the graph's actual semantics.
Quick check
Can you predict the result?
1. Which representation usually uses O(V + E) storage for a sparse graph?
- • An adjacency list
- • A full adjacency matrix
- • A V-by-V table of booleans
2. When can an adjacency matrix be a good choice?
Keep building