What this is
A graph is a set of vertices connected by edges. Every graph algorithm on this site — BFS, DFS, Dijkstra, A* — assumes some way of storing those edges, and that choice quietly determines their performance.
Adjacency Matrix
A V×V grid where M[i][j] = 1 means an edge exists from i to j.
- Edge lookup is O(1) — one array access. Unbeatable.
- Space is O(V²) regardless of edge count. A graph with 10,000 vertices needs 100 million entries even if it has ten edges.
- Listing a vertex's neighbours costs O(V) — you must scan an entire row, mostly zeros.
For an undirected graph the matrix is symmetric, so half of it is redundant.
Adjacency List
An array of lists: each vertex stores only the neighbours it actually has.
- Space is O(V + E) — proportional to real edges, not possible ones.
- Iterating neighbours is O(degree) — exactly what BFS and DFS do at every step, which is why they use lists.
- Edge lookup is O(degree) — you scan the list rather than jumping to it.
The Rule of Thumb
Slide density and watch the two memory figures cross over.
- Sparse graphs (E &lll; V²) — use an adjacency list. Road networks, social graphs and web links are all sparse: most pairs are not connected.
- Dense graphs (E approaching V²) — a matrix becomes competitive on memory and wins outright on lookup speed.
Real-world graphs are overwhelmingly sparse, which is why the adjacency list is the default in practice.
It Changes Algorithm Complexity
This is not just a storage detail. BFS and DFS are O(V + E) with an adjacency list but O(V²) with a matrix, because each vertex must scan a whole row. On a sparse graph with a million vertices that is the difference between seconds and hours.
Similarly, Dijkstra is O(V²) with a matrix and simple scanning, but O((V+E) log V) with an adjacency list and a binary heap.
A Third Option: Edge List
Simply a list of (u, v, weight) triples. Terrible for asking "who are u's neighbours?" but ideal when an algorithm processes every edge in sorted order — which is exactly what Kruskal's MST algorithm does.
Two ways to store the same graph
A graph is a set of vertices and the edges between them. How you store the edges determines what is cheap.
Take this graph: A—B, A—C, B—D, C—D.
Adjacency list — each vertex holds its neighbours:
graph = {
"A": ["B", "C"],
"B": ["A", "D"],
"C": ["A", "D"],
"D": ["B", "C"],
}
Adjacency matrix — a V×V grid where entry [i][j] says whether an edge exists:
A B C D
A [ 0 1 1 0 ]
B [ 1 0 0 1 ]
C [ 1 0 0 1 ]
D [ 0 1 1 0 ]
| Operation | Adjacency list | Adjacency matrix |
|---|
| Is there an edge u—v? | O(degree of u) | O(1) |
| List u's neighbours | O(degree of u) | O(V) |
| Add an edge | O(1) | O(1) |
| Remove an edge | O(degree) | O(1) |
| Space | O(V + E) | O(V²) |
| Iterate all edges | O(V + E) | O(V²) |
Sparse or dense decides it
The space row is what usually settles the choice.
A social network with a million users averaging 200 friends has 200 million edges. An adjacency list stores 200 million entries. An adjacency matrix stores 10¹² — a trillion cells, almost all zero. That is not a trade-off; it is impossible.
Sparse graphs (E much less than V²) are the common case in practice: road networks, social graphs, dependency graphs, web links. Adjacency lists win decisively.
Dense graphs (E approaching V²) do occur — complete graphs, distance matrices between all cities, correlation networks — and there the matrix is competitive and its O(1) edge lookup is genuinely useful.
The practical rule: use an adjacency list unless the graph is dense or you need constant-time edge queries. Most graph algorithms iterate over neighbours, which is exactly what a list makes fast, and their O(V+E) complexity assumes a list.
Weights, direction and the variations
Weighted edges store the weight alongside the neighbour:
graph = {
"A": [("B", 4), ("C", 2)],
"B": [("A", 4), ("D", 5)],
}
In a matrix, the cell holds the weight rather than 1, with infinity (or None) for absence — note that 0 is a poor choice for "no edge" when zero-weight edges are legal.
Directed graphs store each edge once, in the source's list only. An undirected graph stores it twice, once in each endpoint's list — and forgetting the second insertion is one of the most common graph bugs, producing a graph that is silently directed.
Self-loops and parallel edges need deciding: a list handles both naturally, a simple matrix cannot represent parallel edges without storing counts.
For very large sparse graphs there is a third representation worth knowing: compressed sparse row, which stores all neighbours in one flat array with an index array marking where each vertex's neighbours begin. No per-vertex list objects, excellent cache behaviour, and it is what serious graph libraries use internally. The cost is that it is expensive to modify.
The same graph, three ways, with the costs that follow
Choosing between an adjacency matrix and an adjacency list is usually presented as a memory trade. It is also an algorithm-complexity decision: the same traversal has a different big-O depending only on which one you picked, and both facts are worth seeing on the same graph.
Experiments to try
- Start at 30% density. The matrix is mostly zeros — every one of them still occupies memory.
- Switch to the adjacency list. The same graph, stored in a fraction of the space, with only real edges recorded.
- Check an edge in each representation. The matrix jumps straight to the cell; the list scans until it finds it.
- Slide density to 100%. Now the list is storing nearly V² entries too — and the matrix's O(1) lookup makes it the better choice.
- Tick directed and note the matrix loses its symmetry: M[i][j] and M[j][i] become independent.
In one line
A matrix buys O(1) edge lookup with O(V²) memory; a list buys O(V+E) memory with O(degree) lookup. Because real graphs are sparse, adjacency lists are the default — and that choice is what makes BFS and DFS O(V+E) rather than O(V²).
Building one in Python
The idiomatic approach uses defaultdict so nodes appear on first use:
from collections import defaultdict
def build(edges, directed=False):
g = defaultdict(list)
for u, v in edges:
g[u].append(v)
if not directed:
g[v].append(u) # the line people forget
return g
edges = [("A","B"), ("A","C"), ("B","D"), ("C","D")]
graph = build(edges)
Two details worth building in from the start:
Isolated vertices. A vertex with no edges never appears in an edge list, so it will be missing from the graph. If it matters, add all vertices explicitly first.
defaultdict creates keys on read. graph["Z"] returns an empty list and inserts Z, which silently grows the graph during traversal. Use graph.get(node, []) when only reading.
For anything substantial, use a library: networkx for analysis and convenience, scipy.sparse plus scipy.sparse.csgraph for large numerical graphs, and igraph or graph-tool when performance matters.
Where the matrix genuinely wins
Adjacency matrices are not merely the textbook alternative — they have real uses.
Constant-time edge queries. Algorithms that repeatedly ask "is there an edge between these two?" — triangle counting, clique detection — benefit directly.
Linear algebra on graphs. The matrix is a matrix, so it can be multiplied. Aⁿ[i][j] counts walks of length n from i to j. The Laplacian (degree matrix minus adjacency matrix) has eigenvalues that reveal connectivity and cluster structure, which is what spectral clustering uses.
Dense graph algorithms. Floyd-Warshall computes all-pairs shortest paths in O(V³) operating directly on the matrix, and it is the right choice when the graph is dense and all pairs are needed.
GPU computation. Matrix operations parallelise; pointer-chasing through adjacency lists does not. Graph neural networks operate on sparse matrix representations for this reason.
So the choice is not simply "lists are better". It is: lists for traversal on sparse graphs, matrices for algebra and dense algorithms.
Other representations
| Representation | Structure | Use |
|---|
| Edge list | A list of (u, v) pairs | Simple input format; Kruskal's algorithm sorts it |
| Incidence matrix | V×E | Rare; some theoretical work |
| Compressed sparse row | Flat arrays plus offsets | Large static graphs, numerical libraries |
| Implicit | A function generating neighbours | Puzzle states, infinite graphs |
The last row matters more than its obscurity suggests. Many graph problems have no stored graph at all: chess positions, sliding-tile puzzles, word ladders. Neighbours are generated on demand by applying legal moves, and BFS or DFS explores a graph that never exists in memory. The traversal code is identical.
Questions people ask
Which should I use by default? An adjacency list. Most real graphs are sparse and most algorithms iterate over neighbours.
How do I know if my graph is dense? Compare E with V². Above roughly V²/10, matrix representations become competitive.
Do I need to store both directions for an undirected graph? Yes, in an adjacency list. Forgetting it makes the graph directed without any error.
How do I represent a weighted graph? Tuples of (neighbour, weight) in a list, or weights in the matrix cells with infinity for absence.
What about multigraphs? Adjacency lists handle parallel edges naturally; a matrix needs to store counts rather than booleans.
Should I use networkx? For analysis, prototyping and algorithms you would otherwise implement, yes. For hot loops over millions of edges it is slow — use scipy sparse or a compiled library.
Recap in one screen
- Adjacency lists store each vertex's neighbours: O(V+E) space, fast neighbour iteration.
- Adjacency matrices store a V×V grid: O(1) edge lookup, O(V²) space.
- Sparsity decides — and most real graphs are sparse, so lists are the default.
- Undirected edges must be inserted twice in a list; forgetting the second is a silent bug.
- Matrices win for edge queries, linear-algebra methods, dense all-pairs algorithms and GPU work.