A graph is vertices and the pairs that touch
You have climbed a long way to get here: counting iterations, taming recurrences, weighing greedy against dynamic programming. Now the shape of the input changes. A graph is just a set of V vertices (dots) together with a set of E edges (the pairs of dots that are connected). A road map, a friend network, a maze, a web of web pages, the prerequisite chart for these very guides — all of them are graphs the moment you decide what counts as a dot and what counts as a link. The whole point of this rung is to explore such a structure: walk it, search it, and read structure off the walk. But none of that can begin until the graph lives in memory in a form an algorithm can touch.
So before we run a single search, we face a quieter design question: how do we write the graph down? The mathematical object — "these dots, these pairs" — does not tell a machine where to look when it asks "who are the neighbours of vertex 5?" That lookup is the operation every algorithm in this rung performs millions of times, so the way we store the edges is not a detail. It silently sets the running time of everything that follows. The same algorithm can be fast or slow depending only on how its graph was packed.
Two numbers will rule this whole discussion, and it is worth fixing them now. V is the number of vertices and E the number of edges. They are not independent: a simple graph can have at most about V^2 / 2 edges (every pair connected), so E ranges from 0 all the way up to Theta(V^2). When E is near that ceiling we call the graph dense; when E is closer to V — a road map, a social graph where each person knows a few hundred others — we call it sparse. Almost every real graph you meet is sparse, and that single fact tilts the whole storage decision, as we are about to see.
The matrix: one big grid of yes-or-no
The first representation is the most literal. Lay out a V-by-V grid and put a 1 in cell (i, j) when there is an edge from vertex i to vertex j, and a 0 when there is not. That grid is the adjacency matrix. Its great charm is the one question it answers instantly: "is there an edge between u and v?" is a single array lookup, A[u][v], in O(1) time — no searching, just read one cell. If your algorithm spends its life poking at specific pairs and asking *are these two connected?*, the matrix is a gift.
to: 0 1 2 3 # graph: 0-1, 0-2, 1-3 (undirected)
from 0 [ 0 1 1 0 ]
1 [ 1 0 0 1 ]
2 [ 1 0 0 0 ] # row 2 has a single 1 -> vertex 2 has 1 neighbour
3 [ 0 1 0 0 ] # undirected => the grid is symmetric across the diagonalBut that grid charges a steep, unconditional rent. It always occupies Theta(V^2) cells, whether the graph has a million edges or three. A social network of a billion people stored this way would need a billion-squared cells — an impossible 10^18 — even though almost every entry is 0, because most pairs of people are strangers. Worse, the operation we actually need most often — "list the neighbours of u so I can visit them" — forces us to scan u's entire row of V cells, sifting the few 1s out of a sea of 0s. That is O(V) work to find what might be only two or three neighbours.
The list: each vertex keeps its own little address book
The second representation refuses to store the silences. Instead of a giant grid, keep one short list per vertex naming only its actual neighbours. Vertex 0's list reads [1, 2]; vertex 2's list reads just [0]. This is the adjacency list, and its philosophy is exactly opposite to the matrix: it spends memory only on edges that exist, never on edges that do not. Total space is Theta(V + E) — one slot per vertex for its list header, plus one entry per edge (two, for undirected graphs, since each edge appears in both endpoints' books). For a sparse graph where E is around V, that is linear in the input, not quadratic.
Now the trade flips. Listing the neighbours of u — the bread-and-butter move of every search — is just walking u's own short list, costing time proportional to u's actual neighbour count rather than to V. Sum that over a full traversal and the bound is the famous Theta(V + E): every vertex is touched once and every edge is walked once. That clean linear cost is why the breadth-first and depth-first searches in the next two guides are described as running in O(V + E). They inherit that bound directly from the list; on a matrix the very same searches would slow to O(V^2), because each "who are my neighbours?" step would pay O(V) to scan a row.
What does the list give up? The matrix's party trick. To ask "is there an edge between u and v?" on a list, you must scan u's neighbour list looking for v — O(degree of u) in the worst case, not O(1). For most graph searches that question barely comes up, which is why lists win in practice. But for an algorithm built around constant-time edge queries on a dense graph, the matrix's instant lookup can be worth its quadratic rent. Neither structure is simply "better"; each is tuned for a different question.
Choosing honestly: it depends on density and on what you ask
Put the two side by side and the rule of thumb almost writes itself. The adjacency list costs Theta(V + E) space, lists a vertex's neighbours in time proportional to its degree, and answers "is uv an edge?" in O(degree). The adjacency matrix costs Theta(V^2) space, lists neighbours in O(V) (you scan a whole row), and answers "is uv an edge?" in O(1). For sparse graphs — the overwhelming common case, and what almost every guide in this rung assumes — the list wins on both space and traversal speed. For dense graphs where E is already Theta(V^2), the matrix's space is no longer wasteful and its O(1) edge test becomes a genuine advantage.
Be honest about what the Theta(V + E) bound is and is not, because it is easy to over-read. It is asymptotic, so it describes scaling, not a verdict at every size: for a tiny graph the matrix's flat array can beat the list's pointer-chasing on real hardware, since contiguous cells are cache-friendly and the hidden constants favour the simpler layout. And V + E is genuinely the right measure of input size for a graph — two numbers, not one — so an O(V + E) algorithm reading every vertex and edge once is, refreshingly, optimal: you cannot solve a problem in less time than it takes to look at the input.
Variations the representation has to carry
Real graphs come in flavours, and both representations bend to fit. A directed graph has one-way edges (a web link, a prerequisite, a Twitter follow): in the matrix, A[u][v] = 1 no longer forces A[v][u] = 1, so the grid loses its diagonal symmetry; in the list, the edge u -> v lives only in u's neighbour list, never in v's. An undirected graph stores each edge in both places, which is why an undirected adjacency list holds 2E entries. A weighted graph attaches a number to each edge — a distance, a cost, a capacity: the matrix simply stores the weight in the cell instead of a bare 1, and the list stores a (neighbour, weight) pair instead of just a neighbour.
These choices are not bookkeeping trivia; they wire directly into the algorithms ahead. The undirected, unweighted list is exactly the substrate on which the next guide builds a BFS to count shortest paths in edges and to test whether a graph splits cleanly into two sides. The directed list is what a later guide walks to produce a topological order or to peel out connected components. Weighted graphs are the ground the shortest-path rung stands on. The representation is the stage; every later algorithm is a play that can only run on a stage built to hold it.