A graph is just things and the connections between them. The things are called vertices (or nodes); the connections are called edges. Friend networks, road maps, web links, course prerequisites — all graphs. Before you can search a graph, you have to store one. This lesson is about that: how to model a graph in code. The next lesson covers walking through it.
Step through the animation on the right. We reveal the vertices, then the edges, then build the graph's adjacency list — and finally light up one vertex and its neighbors.
The idea
Draw the graph and you see vertices joined by edges. To put that in code, the most common shape is the adjacency list: for every vertex, store a list of the vertices it connects to. That is it — a lookup table from each vertex to its neighbors.
Our example is undirected: an edge between A and B means you can travel both ways, so A appears in B's list and B appears in A's list. If edges had a direction (a one-way street, a "follows" link), you would only add the connection one way.
There is a second common way to store a graph, the adjacency matrix: an n × n grid where cell (i, j) is 1 if vertex i connects to vertex j, and 0 otherwise. It makes "is X connected to Y?" an instant lookup, but it always uses O(n²) space even when there are very few edges. The adjacency list only stores the edges that actually exist, so for most real graphs (which are sparse) it wins.
Walk through it
Press Play on the right, or step with Next / Back. Watch the graph get built in stages:
- First the five vertices appear — five dots, no connections.
- Then the edges snap in, turning the dots into a connected graph.
- Then we build the adjacency list one row at a time. As each vertex lights up, its row appears with the list of neighbors.
- Finally we focus on vertex B. Its neighbors (A, C, D) turn green, the rest dim out — and notice we found them just by reading B's row.
The code panel highlights the matching line: the dict entry as each row is built, then the lookup loop at the end.
The code, line by line
# Undirected graph as an adjacency list (dict of lists)
graph = {
"A": ["B", "C"],
"B": ["A", "C", "D"],
"C": ["A", "B", "E"],
"D": ["B"],
"E": ["C"],
}
# Neighbors of a vertex — O(1) lookup, then iterate
for neighbor in graph["B"]:
print(neighbor)- The graph is a dict of lists. The keys are the vertices; each value is that vertex's list of neighbors.
- Because the graph is undirected, every edge is written twice:
"A": [..., "B"]and"B": [..., "A"]. The two halves must agree. - To get a vertex's neighbors, you index the dict:
graph["B"]. That is anO(1)lookup, and it hands you exactly the list["A", "C", "D"]. - Lines 11 and 12 (highlighted) loop over those neighbors. This tiny loop is the building block every traversal — BFS and DFS — is built on.
Complexity
| Case | Time | Notes |
|---|---|---|
| Add edge | O(1) (fast) | append to two lists |
| Find a vertex's neighbors | O(1) (fast) | one dict lookup returns the list |
| Check if edge (u, v) exists | O(deg) (moderate) | scan u's neighbor list |
O(V + E) (moderate)The space is O(V + E): one entry per vertex (V) plus one list slot per edge end (E). That is why the adjacency list beats the matrix for sparse graphs — a matrix is always O(V²), even if almost no edges exist.
When to use / pitfalls
Reach for an adjacency list by default — it is the standard representation in interviews and
real code, and O(V + E) space matches almost every graph you will meet. Use an adjacency
matrix only when the graph is small and dense, or when you need constant-time "is there an edge
between these two?" checks.
In an undirected graph, every edge must appear in both vertices' lists. Adding B to A's
list but forgetting to add A to B's list is the classic bug — half your edges silently go
one-way, and a later traversal misses them.
Practice
In our undirected graph, B's list is [A, C, D]. Without looking at the other rows, which three vertices are guaranteed to have B in their own list?
1. What is an adjacency list?
2. In an undirected graph, how many times is each edge stored in an adjacency list?
3. Why is an adjacency list usually preferred over an adjacency matrix?
4. Given graph = {"B": ["A", "C", "D"], ...}, how do you get B's neighbors?