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

Before any symbol: we will use the letter $V$ for how many dots (vertices) are in our graph, and $E$ for how many lines (edges) connect them. That is all $V$ and $E$ ever mean. Let's earn everything else.

Step 1 — What a graph actually is (dots and lines)

WHAT. We draw the four dots and the four friendships ${0, 1}, {0, 2}, {1, 2}, {2, 3}$ .

WHY. Every storage decision below is a decision about how to write this picture down in memory. You cannot judge "wasteful" or "efficient" without the picture in front of you.

PICTURE. Look at the figure: four blue dots, four orange lines. Count them — $V = 4$ dots, $E = 4$ lines. Notice vertex $2$ is popular (touches three others) while vertex $3$ is lonely (touches only one).

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

Step 2 — The grid idea: reserve a box for every pair

WHAT. Draw a checkerboard with all $V$ dots along the top and the same $V$ dots along the side. Every little box sits at a crossing of one top-dot and one side-dot — i.e. one ordered pair $(u, v)$ .

WHY a grid and not something cleverer? Because we want the fastest possible answer to "is $u$ – $v$ an edge?". A grid gives it a fixed home address (row $u$ , column $v$ ) so we can jump straight there. No searching. That speed is the whole reason the grid exists.

PICTURE. The figure shows the empty $4 \times 4$ grid. Count the boxes: 4 rows $\times$ 4 columns $= 16$ boxes. We reserved a box for the friendship $0$ – $1$ and for the non-friendship $0$ – $3$ — the grid does not care whether the edge exists, it books a box either way.

Step 3 — Fill the grid: this is the adjacency matrix

WHAT. Put a $1$ (green) in a box when its two dots are friends, a $0$ (gray) when they are not.

WHY. We are converting the picture (Step 1) into numbers a computer can index. The $1$ / $0$ choice is the simplest encoding of "yes edge / no edge."

PICTURE. Look at row 2 (vertex 2) in the figure: green $1$ s sit in columns $0, 1, 3$ — exactly the three friends of vertex 2 — and a gray $0$ in column $2$ (you are not your own friend, no self-loop).

$A = 0110101011010010$

Each entry: $A [u] [v] = 1$ means row-dot $u$ shakes hands with column-dot $v$ .

Step 4 — Count the grid's cost: where $O (V^{2})$ is born

WHAT. Count every box we reserved: $V$ rows times $V$ columns.

WHY. "Space cost" = how many memory slots we occupy. Every box is one slot, occupied whether it holds a $1$ or a lonely $0$ .

PICTURE. In the figure, the $4$ green boxes are real friendships; the $12$ gray boxes are wasted — reserved for pairs who are not friends. Same total either way.

$boxes = rows V \times columns V = V^{2} = O (V^{2})$

The $O ()$ (Big-O Notation) means "grows like" — for large $V$ the cost climbs like $V^{2}$ . For our tiny graph $V^{2} = 16$ boxes to store just $4$ edges: already $12/16 = 75%$ wasted.

Step 5 — A different idea: give each dot a sticky note

WHAT. Throw away the grid. Instead give each of the $V$ dots one sticky note that names only its actual friends.

WHY a list and not the grid? Because the grid's gray boxes were pure waste. A sticky note writes down a friend only when the friendship exists — so nothing is spent on the millions of non-friendships. We trade instant lookup for tiny size.

PICTURE. The figure shows four sticky notes. Vertex 3's note is nearly empty ([2]); vertex 2's note is the longest ([0,1,3]). Note length matches popularity — this is the key difference from the fixed-size grid rows.

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

Step 6 — Count the sticky notes: where $O (V + E)$ is born

WHAT. Add up: $V$ note-headers, plus one written name for every edge-endpoint.

WHY two names per edge? Friendship ${0, 1}$ must appear on note 0 (so 0 can find 1) and on note 1 (so 1 can find 0). Look back at Step 5: 1 is on note 0 and 0 is on note 1. Undirected ⇒ each edge is written twice.

PICTURE. In the figure, colored arrows pair up the two copies of each edge. Count the names across all notes: $2 + 2 + 3 + 1 = 8 = 2 E$ . Add the $4$ note-headers.

$entries = note headers V + two names per edge 2 E = O (V + E)$

For our graph: $4 + 8 = 12$ entries. (In a directed graph you'd write each edge once → $V + E$ .)

Step 7 — The degenerate cases (never leave a scenario unshown)

WHAT. Compare the two representations at the boundaries.

WHY. A formula you only tested in the middle can lie at the edges. We check both ends so no reader hits a surprise.

PICTURE. The figure has two panels:

Empty graph ( $E = 0$ ): grid still books $V^{2}$ gray boxes (huge waste); sticky notes cost just $V$ empty headers. List wins by a mile — this is a sparse graph.
Complete graph ( $E = (2 V)$ , everyone friends with everyone): every box is green, and every note is nearly full. Now $2 E \approx V^{2}$ , so the list is also $O (V^{2})$ — no size win — and the grid gives $O (1)$ lookups on top. Matrix wins — a dense graph.

$empty 0 \leq E \leq complete (2 V) = \frac{V ( V - 1 )}{2} = O (V^{2})$

Here $(2 V)$ ("V choose 2") counts how many pairs of dots exist — the maximum possible number of undirected edges.

Recall Self-test the extremes

On an empty graph, which representation wastes memory ::: The matrix — $V^{2}$ boxes for $0$ edges; the list costs only $V$ . When does the list's size stop beating the matrix ::: On a dense graph where $E = Θ (V^{2})$ , since $2 E \approx V^{2}$ .

The one-picture summary

This is why traversals like Breadth-First Search (BFS) and Depth-First Search (DFS) run in $O (V + E)$ on lists (they only walk real edges), while Floyd-Warshall Algorithm and edge-heavy matrix tricks prefer the grid's $O (1)$ lookups. Dijkstra's Algorithm on a sparse graph also rides the list.

Recall Feynman retelling (say it to a 12-year-old)

Four kids; some are friends. Grid way: draw a checkerboard with every kid on the top and side, tick a box for each friendship. Checking any pair is instant — but you drew a box for every possible pair, so most boxes sit empty and wasted. Its size is $V \times V = V^{2}$ , no matter how few friendships exist. Sticky-note way: give each kid a note listing only their friends. Tiny when friendships are rare. Its size is $V$ notes plus two names per friendship ( $2 E$ ), so $V + E$ . Few friends → sticky notes (list). Everyone-knows-everyone → the grid is just as small and faster, so use the grid (matrix).