Adjacency Matrix & Adjacency List
Two ways to store a graph in memory, what each costs, and when to choose which.
Rule of this site: Don't just watch: implement it yourself, then solve 2–3 problems.
02Mental model
Two ways to write down who knows whom in a class.
A big table (adjacency matrix): rows and columns are students, and you put a 1 where two students know each other. Checking any pair is instant, but a class of 1,000 needs a million cells, mostly zeros.
A contact list per student (adjacency list): each student keeps a list of only the people they know. It is compact, and listing a student’s friends is fast. But checking “does A know B?” means scanning A’s list.
Adjacency matrix
int m[V][V] = {};
m[u][v] = m[v][u] = 1; // undirected edge u–v- Space O(V²), whatever the number of edges.
- Edge check O(1).
- Symmetric for undirected graphs. For weighted graphs, store the weight instead of 1.
Adjacency list
vector<vector<int>> adj(V);
adj[u].push_back(v);
adj[v].push_back(u); // undirected: both ends- Space O(V + E).
- Looping over neighbours costs only deg(u).
Which one?
- Sparse graphs (most real ones): list.
- Dense graphs, or when you need many fast “is there an edge?” checks: matrix.
03Visualize
space play · ←→ step · r reset. The highlighted code line follows each step.
Build the undirected graph and toggle between matrix and list. Then build the directed one and see the matrix lose its symmetry.
04C++ code
Compiled and run with g++ -std=c++17; the output below is real. Type it out yourself before you copy it.
#include <iostream>
#include <vector>
using namespace std;
const int V = 6;
int main() {
int edges[][2] = {{0, 1}, {0, 3}, {1, 2}, {1, 4}, {3, 4}, {2, 5}, {4, 5}};
int matrix[V][V] = {}; // O(V²) space
vector<vector<int>> list(V); // O(V + E) space
for (auto& e : edges) {
int u = e[0], v = e[1];
matrix[u][v] = matrix[v][u] = 1; // undirected: both directions
list[u].push_back(v);
list[v].push_back(u);
}
cout << "Adjacency matrix:\n ";
for (int j = 0; j < V; j++) cout << j << " ";
cout << "\n";
for (int i = 0; i < V; i++) {
cout << i << ": ";
for (int j = 0; j < V; j++) cout << matrix[i][j] << " ";
cout << "\n";
}
cout << "Adjacency list:\n";
for (int i = 0; i < V; i++) {
cout << i << " ->";
for (int v : list[i]) cout << " " << v;
cout << " (degree " << list[i].size() << ")\n";
}
cout << "edge 1-4? " << (matrix[1][4] ? "yes" : "no") << ", edge 0-5? " << (matrix[0][5] ? "yes" : "no") << "\n";
}Adjacency matrix: 0 1 2 3 4 5 0: 0 1 0 1 0 0 1: 1 0 1 0 1 0 2: 0 1 0 0 0 1 3: 1 0 0 0 1 0 4: 0 1 0 1 0 1 5: 0 0 1 0 1 0 Adjacency list: 0 -> 1 3 (degree 2) 1 -> 0 2 4 (degree 3) 2 -> 1 5 (degree 2) 3 -> 0 4 (degree 2) 4 -> 1 3 5 (degree 3) 5 -> 2 4 (degree 2) edge 1-4? yes, edge 0-5? no
05Complexity
| space | matrix O(V²) · list O(V + E) |
|---|---|
| is there an edge u–v? | matrix O(1) · list O(deg u) |
| visit all neighbours of u | matrix O(V) · list O(deg u) |
| add an edge | matrix O(1) · list O(1) |
For BFS/DFS the list gives O(V + E) and the matrix gives O(V²).
06Watch
Graph Representation: Adjacency Matrix
Why this one: The adjacency matrix, its cost, and when it wastes space.
Graph Representation: Adjacency List
Why this one: The adjacency list and a clear side-by-side cost comparison.
07Exam lens
Likely questions
- Draw the adjacency matrix and adjacency list of a given graph.
- Compare the space and time costs of the two representations.
- Which representation suits a sparse graph? A dense one? Why?
- How do you store a weighted graph in each representation?
Common mistakes
- Setting only
m[u][v]for an undirected edge. Setm[v][u]too. - Saying the list is always better. Edge lookup is O(1) only in the matrix.
- Forgetting that an undirected edge appears twice in the list.
08Quick check
09Practice
🟢 Trace by hand
Vertices 0–3, undirected edges 0–1, 0–2, 1–2, 2–3. Write the adjacency matrix and adjacency list.
Show answer
0 1 2 3
0: 0 1 1 0
1: 1 0 1 0
2: 1 1 0 1
3: 0 0 1 0List: 0 → 1 2 · 1 → 0 2 · 2 → 0 1 3 · 3 → 2
🟡 Implement it
Store a weighted undirected graph both ways. Use vector<vector<pair<int,int>>> for the list (neighbour, weight) and 0 for "no edge" in the matrix.
Hint
adj[u].push_back({v, w}); adj[v].push_back({u, w}); m[u][v] = m[v][u] = w;
🔴 Solve problems
Hint
Build an adjacency list from the edge array, then BFS or DFS from source.
Hint
Count degrees with a list. The center has degree n − 1.
10Mastery checklist
Tick these honestly. When every box is ticked, the topic is marked complete.