Graphs and their representations
Adjacency lists, matrices and edge lists compared, how directed and weighted edges change the storage, degree and connectivity basics, and how to pick based on density.
Three ways to store the same graph
# vertices: 0..4
edges = [(0,1), (0,2), (1,3), (2,3), (3,4)]
# adjacency list — dict or list of lists
adj = {i: [] for i in range(5)}
for u, v in edges:
adj[u].append(v)
adj[v].append(u) # omit for a directed graph
# adjacency matrix — O(V^2) memory
V = 5
matrix = [[0] * V for _ in range(V)]
for u, v in edges:
matrix[u][v] = 1
matrix[v][u] = 1
# weighted: store (neighbour, weight) pairs
wadj = {i: [] for i in range(5)}
wadj[0].append((1, 4.5)) # edge 0->1 costs 4.5| Representation | Memory | Has edge u-v? | List neighbours |
|---|---|---|---|
| Adjacency list | O(V + E) | O(deg u) | O(deg u) |
| Adjacency matrix | O(V^2) | O(1) | O(V) |
| Edge list | O(E) | O(E) scan | O(E) scan |
| Incidence matrix | O(V x E) | O(deg u) | O(E) |
Dense or sparse decides it
The ratio E to V² is the whole decision. A social graph with a million users and fifty edges each is sparse; a small complete graph of a thousand nodes is dense. Sparse graphs want lists, dense graphs can afford matrices.
# degree and a simple BFS over an adjacency list
def bfs(adj, start):
seen = {start}
queue = collections.deque([start])
order = []
while queue:
u = queue.popleft()
order.append(u)
for v in adj[u]:
if v not in seen:
seen.add(v)
queue.append(v)
return order- Undirected graphs store each edge twice in a list, which is why memory is O(V + 2E).
- A matrix entry answers "is there an edge" in constant time, at the cost of touching V cells to list neighbours.
- Edge lists are ideal for algorithms that process every edge once: Kruskal, Bellman-Ford, external-memory sorts.
- For a weighted graph, store the weight next to the neighbour, or keep a parallel weight matrix.
The traps that bite in practice
| Trap | Symptom | Fix |
|---|---|---|
| Recursive DFS on a deep graph | Stack overflow | Use an explicit stack |
| Missing reverse edge | Directed traversal that should be undirected | Add both directions on insert |
| Duplicate edges | Wrong degree counts, slower traversal | Deduplicate, or use a set per vertex |
| Self-loops unchecked | Infinite loops in some algorithms | Decide and document whether loops are allowed |
| Assumed connected | Silent partial results | Loop over all vertices, not just the start |
⚠️
Always handle disconnected graphs explicitly. Algorithms that start from vertex 0 and stop when the queue empties return only the first component, and the missing half of the answer looks like a legitimate result rather than an error.
FAQ
When is an adjacency matrix worth the memory?
When the graph is dense, when you need constant-time edge existence, or when you want to do matrix operations such as transitive closure by repeated multiplication.
How do I store a graph with millions of edges?
Use compressed sparse row (CSR): one array of neighbour ids and one array of offsets per vertex. It is the adjacency list flattened, with far better cache behaviour and no per-vertex object overhead.
Related
Union-Find and disjoint sets Tries and prefix trees
Last refreshed 2026-09-18.