The same graph, stored two ways. One answers “are these connected?” instantly but wastes memory; the other is compact but must scan. Toggle between them and watch the costs swap.
Controls
vertices6
density30%
Same Graph, Two Storages
step 0
Insight
A graph is vertices plus edges. How you store the edges decides which operations are cheap.
vertices V6
edges E0
matrix memory0
list memory0
Complexity
Matrix edge checkO(1)
List edge checkO(degree)
Matrix spaceO(V²)
Graph Representations
Before BFS, DFS or Dijkstra can run, the graph has to live somewhere.
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:
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:
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.
example_01.pyPython
EDGES = [(0, 1), (0, 2), (1, 3), (2, 3), (3, 4)]
V = 5
def as_matrix(edges, v):
m = [[0] * v for _ in range(v)]
for a, b in edges:
m[a][b] = m[b][a] = 1
return m
def as_list(edges, v):
adj = {i: [] for i in range(v)}
for a, b in edges:
adj[a].append(b)
adj[b].append(a)
return adj
matrix = as_matrix(EDGES, V)
adj = as_list(EDGES, V)
print("adjacency matrix:")
print(" " + " ".join(str(i) for i in range(V)))
for i, row in enumerate(matrix):
print(" %d %s" % (i, " ".join(str(x) for x in row)))
print()
print("adjacency list:")
for k, vs in adj.items():
print(" %d -> %s" % (k, vs))
print()
print("edge list:", EDGES)
# Three encodings of one graph. Now the two questions you actually ask,
# and how many cells each representation touches to answer them.
def matrix_has_edge(m, a, b):
return m[a][b] == 1, 1 # one lookup
def list_has_edge(adj, a, b):
return b in adj[a], len(adj[a]) # scans the neighbour list
def matrix_neighbours(m, a):
return [i for i, x in enumerate(m[a]) if x], len(m[a]) # scans the row
def list_neighbours(adj, a):
return adj[a], len(adj[a]) # already the answer
print()
print('"is there an edge 1-3?" matrix: %s in %d cell(s) | list: %s in %d' % (
matrix_has_edge(matrix, 1, 3)[0], matrix_has_edge(matrix, 1, 3)[1],
list_has_edge(adj, 1, 3)[0], list_has_edge(adj, 1, 3)[1]))
print('"who neighbours 3?" matrix: %s in %d cell(s) | list: %s in %d' % (
matrix_neighbours(matrix, 3)[0], matrix_neighbours(matrix, 3)[1],
list_neighbours(adj, 3)[0], list_neighbours(adj, 3)[1]))
# Each wins one of them. The matrix answers "is there an edge" in one
# lookup and pays V cells to list a node's neighbours; the list is the
# other way round. Traversals ask the second question at every node,
# which is why the choice changes their complexity:
#
# BFS/DFS on an adjacency list: O(V + E)
# BFS/DFS on an adjacency matrix: O(V^2)
#
# On a sparse graph that is the difference between linear and quadratic,
# for identical traversal code.
print()
print("%10s %12s %16s %16s %10s" % (
"V", "E (sparse)", "matrix cells", "list entries", "matrix/list"))
for v in (10, 100, 1000, 10000):
e = 3 * v
print("%10d %12d %16d %16d %10.0fx" % (
v, e, v * v, 2 * e, (v * v) / (2 * e)))
# A social graph with a million users and a hundred friends each: the
# list holds two hundred million entries, and the matrix would need a
# trillion cells, almost all of them zero. That is why adjacency lists
# are the default and the matrix is reserved for dense graphs, or for
# the algorithms that genuinely want the matrix -- Floyd-Warshall walks
# it directly, and its O(V^3) is stated in those terms for that reason.
Output
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.
Run it in Python
The same six-node graph stored three ways, with the cost of each question measured against each store. Nothing here is an opinion — the memory figures come from sys.getsizeof and the operation counts are counted.
representations.pyPython 3
# One graph, three representations, and what each one is good at.
edges = [("A", "B"), ("A", "C"), ("B", "D"), ("C", "D"),
("D", "E"), ("E", "F")]
nodes = ["A", "B", "C", "D", "E", "F"]
# 1. Edge list - just the pairs.
print("edge list :", edges)
# 2. Adjacency list - for each node, who it reaches.
adj_list = {n: [] for n in nodes}
for u, v in edges:
adj_list[u].append(v)
adj_list[v].append(u) # undirected: store both directions
print("adj list :", adj_list)
# 3. Adjacency matrix - a full V x V grid of yes/no.
index = {n: i for i, n in enumerate(nodes)}
matrix = [[0] * len(nodes) for _ in nodes]
for u, v in edges:
matrix[index[u]][index[v]] = 1
matrix[index[v]][index[u]] = 1
print("adj matrix:")
print(" " + " ".join(nodes))
for n in nodes:
row = " ".join(str(x) for x in matrix[index[n]])
print(f" {n} {row}")
print()
# "Is there an edge A-D?" - one lookup vs a scan.
print("matrix answers 'A-D?' in one step :", bool(matrix[index["A"]][index["D"]]))
print("list scans A's neighbours :", "D" in adj_list["A"], f"({len(adj_list['A'])} checked)")
print()
# "Who does D reach?" - a scan vs a direct read.
row_scan = [nodes[i] for i, x in enumerate(matrix[index["D"]]) if x]
print("matrix scans a whole row of", len(nodes), ":", row_scan)
print("list reads the answer directly :", adj_list["D"])
print()
V, E = len(nodes), len(edges)
print(f"V = {V}, E = {E}")
print(f"matrix cells : V*V = {V * V} (of which {2 * E} are 1s)")
print(f"list entries : 2*E = {2 * E}")
print("Sparse graphs waste most of a matrix. Dense ones make the list slower.")
Output
How the code works
adj_list[u].append(v); adj_list[v].append(u)Both directions, because the graph is undirected. Drop the second line and you have a directed graph — that one line is the entire difference in code.
matrix = [[0] * len(nodes) for _ in nodes]V×V cells allocated up front, whether or not there are edges to put in them. For a social network of a million users that is 10¹² cells to store a few hundred million edges.
matrix[index["A"]][index["D"]]Constant time, and unbeatable. If the question your program asks most often is “are these two connected?”, this is the representation.
adj_list["D"]Also constant time, and it returns the neighbours themselves. Traversal algorithms — BFS, DFS, Dijkstra — ask this question and never the other one, which is why they all assume an adjacency list.
V*V versus 2*EThe whole trade-off in two numbers. Matrices cost O(V²) always; lists cost O(V + E), which is smaller exactly when the graph is sparse — and real graphs almost always are.
Change one thing
Add the edges to make the graph complete (every node to every other). The matrix cost does not move; the list cost climbs to meet it.
Delete the adj_list[v].append(u) line and print the result. You now have a directed graph, and adj_list["F"] is empty.
Store weights instead of 1s in both structures. The matrix takes it without a change of shape; the list has to hold pairs.
Where this runs
Real CPython, compiled to WebAssembly and running on your own machine — nothing is uploaded. The first run takes a few seconds while the interpreter downloads; after that it is immediate. Need more room, or want to paste your own attempt? Use the Python compiler.
Check yourself
0 of 3
Answer without scrolling back up.
For a sparse graph, an adjacency matrix wastes space because it stores:
The grid is allocated up front. A million users with a few hundred million friendships would need 10¹² cells to hold them.
"Is there an edge between A and D?" is answered fastest by:
One indexed read. The list has to scan A's neighbours and the edge list has to scan everything.
BFS, DFS and Dijkstra all assume an adjacency list because they ask:
Traversals iterate a node's neighbours, which a list returns directly and a matrix only finds by scanning a whole row of V cells.
Cheat sheet
Graph Representations
The same graph, stored two ways. One answers “are these connected?” instantly but wastes memory; the other is compact but must scan. Toggle between them and watch the costs swap.
Ashish Jangra builds and maintains VizLearn. Every module here is written and the visualisation behind it hand-built, so the numbers in a readout come from the same code that draws the picture. Corrections are genuinely welcome and get priority over everything else — if a page states something wrong, or an animation misrepresents what the algorithm does, get in touch.