Representations — adjacency matrix (space O(V²)), adjacency list (space O(V+E))

WHAT are we representing?

The key fact controlling all space costs: $0 \le E \le \binom{V}{2} = \frac{V(V-1)}{2} = O(V^2)\quad(\text{undirected, no self-loops})$

So at most there are $\sim V^2/2$ edges. A graph where $E \approx V^2$ is called dense; one where $E \approx V$ (or $E \ll V^2$ ) is called sparse. This single distinction decides which representation wins.

Representation 1 — Adjacency Matrix

WHY it costs $O(V^2)$ : we allocate one cell for every ordered pair $(u,v)$ — that's $V \times V = V^2$ cells — regardless of how many edges actually exist. Even an empty graph with $V=1000$ eats a million cells.

Representation 2 — Adjacency List

WHY it costs $O(V+E)$ : we store the $V$ list headers ( $+V$ ) plus, across all lists, exactly one entry per edge-endpoint. Each undirected edge appears in two lists, so total entries $= 2E = O(E)$ . Directed: $E$ entries. Sum: $O(V+E)$ . Nothing is stored for absent edges — that's the saving.

Figure — Representations — adjacency matrix (space O(V²)), adjacency list (space O(V+E))

HOW they compare (the 80/20 table)

Operation	Adjacency Matrix	Adjacency List
Space	$O(V^2)$	$O(V+E)$
Edge query `isEdge(u,v)?`	$O(1)$ ✅	$O(\deg u)$
List neighbors of $u$	$O(V)$ (scan whole row)	$O(\deg u)$ ✅
Add edge	$O(1)$	$O(1)$
Iterate all edges	$O(V^2)$	$O(V+E)$ ✅
Best for	dense graphs / fast edge checks	sparse graphs (the common case)

Worked Examples

Worked example Example 1 — Build both for a tiny undirected graph

Vertices $\{0,1,2,3\}$ , edges $\{0,1\},\{0,2\},\{1,2\},\{2,3\}$ .

Matrix (symmetric): $A=\begin{pmatrix}0&1&1&0\\1&0&1&0\\1&1&0&1\\0&0&1&0\end{pmatrix}$ Why this step? Row 2 (vertex 2) has 1s in columns 0,1,3 because 2 touches those three vertices.

List:

0 -> [1, 2]
1 -> [0, 2]
2 -> [0, 1, 3]
3 -> [2]

Why this step? Edge $\{0,1\}$ appears in both adj[0] and adj[1] — undirected means store both directions. Total entries $=2E=8$ . ✔

Common Mistakes (Steel-manned)

Active Recall

Recall Quick self-test (hide and answer)

Why exactly $O(V^2)$ for the matrix even with few edges?
Why $2E$ and not $E$ entries for an undirected list?
Which representation makes isEdge(u,v) $O(1)$ ?
For which graph type do their space costs become equal?

Answers: 1) one cell per ordered pair, edges irrelevant. 2) edge stored in both endpoints' lists. 3) matrix. 4) dense, $E=\Theta(V^2)$ .

Adjacency matrix space complexity

O(V^2)

— one cell per ordered pair of vertices

Adjacency list space complexity

O(V+E)

—

V

headers plus

2E

(undirected) edge entries

Why is matrix

O(V^2)

even when the graph has few edges

It allocates a cell for every pair

(u,v)

regardless of whether the edge exists

How many list entries does one undirected edge create

Two — it is stored in both endpoints' neighbor lists

Time to check isEdge(u,v) in a matrix

O(1)

— direct index A[u][v]

Time to check isEdge(u,v) in a list

O(\deg u)

— must scan u's neighbor list

Time to list all neighbors of u in a matrix

O(V)

— scan the entire row

Time to list all neighbors of u in a list

O(\deg u)

Default representation for sparse graphs

Adjacency list

When does the matrix's space tie with the list's

Dense graphs where

E=\Theta(V^2)

Property of an adjacency matrix for an undirected graph

It is symmetric,

A=A^T

Meaning of

(A^k)[u][v]

Number of walks of length exactly

k

from

u

v

Max number of edges in an undirected simple graph on V vertices

\binom{V}{2}=\frac{V(V-1)}{2}

Recall Feynman: explain to a 12-year-old

Imagine your class and who is friends with whom. Method 1 (grid / matrix): draw a big checkerboard with every kid's name on the top and side. Put an ✗ in a square if those two are friends. Super fast to check any pair — but you waste a square even for the millions of pairs who aren't friends. Big class = giant grid. Method 2 (lists): give each kid a sticky note listing only their friends. Tiny if friendships are few. To check if Amy and Ben are friends you read Amy's note — a little slower, but no wasted space. Few friendships → use sticky notes (list). Everyone-knows-everyone → use the grid (matrix).

Connections

Breadth-First Search (BFS) — runs in $O(V+E)$ because it uses adjacency lists.
Depth-First Search (DFS) — same $O(V+E)$ traversal bound.
Floyd-Warshall Algorithm — prefers the adjacency matrix ( $O(1)$ edge weight access).
Dijkstra's Algorithm — adjacency list + priority queue for sparse graphs.
Big-O Notation — the space/time trade-off vocabulary used here.
Sparse vs Dense Graphs — the property that decides the choice.
Matrix Multiplication — explains $(A^k)$ counting walks.

Concept Map

Hinglish (regional understanding)

Intuition Hinglish mein samjho

Dekho, graph ka matlab hai "kaun kis se connected hai." Ab computer me ye connection store karne ke do main tareeke hain. Pehla hai adjacency matrix — ek $V \times V$ ka grid bana lo, har cell A[u][v] me 1 likho agar edge hai, warna 0. Problem ye hai ki chahe edges 4 ho ya 0, tum har pair ke liye ek box reserve karte ho, isliye space $O(V^2)$ ho jaata hai. Plus point: "kya u aur v ke beech edge hai?" ye sawaal $O(1)$ me answer ho jaata hai — bas index karo.

Doosra tareeka hai adjacency list — har vertex ke liye sirf uske actual neighbors ki ek list rakho. Yahan tum absent edges ke liye kuch store hi nahi karte, isliye space sirf $O(V+E)$ — $V$ headers plus har undirected edge ke do entries ( $2E$ ). Ye real-world graphs ke liye perfect hai kyunki zyadatar graphs sparse hote hain (edges kam, vertices zyada). Bas thoda dhyaan: edge check karne ke liye list me $O(\deg u)$ time lagta hai, instant nahi.

Yaad rakhne ka simple rule: agar graph dense hai (sabhi sabse connected, jaise $E \approx V^2$ ) ya $V$ chhota hai ya tumhe baar-baar fast edge check chahiye (jaise Floyd-Warshall me), to matrix lo. Warna by default list hi best hai — BFS/DFS bhi list ke saath $O(V+E)$ me chalte hain, jo bahut fast hai. Bas ye trade-off — space vs edge-query speed — pura topic isi pe ghoomta hai.

Representations — adjacency matrix (space O(V²)), adjacency list (space O(V+E))

WHAT are we representing?

Representation 1 — Adjacency Matrix

Representation 2 — Adjacency List

HOW they compare (the 80/20 table)

Worked Examples

Common Mistakes (Steel-manned)

Active Recall

Connections

Concept Map

Hinglish (regional understanding)

Go deeper — visual, from zero

Test yourself — Graphs

Connections