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.
Quick Context
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.
Interactive Exploration Guide
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.
Key Takeaway
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²).
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.