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

Before you can compare an adjacency matrix with an adjacency list, you must be able to read every symbol the parent note throws at you. Below, each symbol is built from nothing — plain words first, then the picture, then why the topic can't live without it. Read top to bottom; each one leans on the one above.

1. The dot: a vertex

Look at the figure below: four dots, labelled $0,1,2,3$. In coding we number our things starting from $0$ (not $1$) because array slots are numbered from $0$. So "vertex 2" is just "the dot we chose to call 2."

Why the topic needs it: every storage method has to have a name for each thing so it can say "thing 2 is connected to thing 0." No dots, nothing to connect.

2. The line: an edge

In the figure above, the line between dot $0$ and dot $1$ is the edge that says "0 and 1 are friends."

Two flavours, shown side by side below:

• Undirected edge — a plain line. Friendship: if you are my friend, I am yours. Written with curly braces $\{u,v\}$ because the order does not matter: $\{0,1\}$ and $\{1,0\}$ are the same line.
• Directed edge — an arrow. "Follows on social media": I can follow you without you following me. Written with round braces $(u,v)$, an ordered pair, because $u\to v$ is not the same as $v\to u$.

Why the topic needs it: the edges are the information we're storing. Everything else is bookkeeping around them.

3. The letters $u$ and $v$: generic vertex names

Think of $u$ and $v$ like the "$x$" in "let $x$ be a number" — a stand-in so we can talk about the rule without naming a specific dot. In A[u][v] the $u$ picks a row and $v$ picks a column.

Why the topic needs it: the storage rules ("store the edge in adj[u] and adj[v]") must work for every pair, so we describe them with placeholders.

4. The whole picture: $G=(V,E)$

Why the topic needs it: every sentence in the parent ("a $V\times V$ matrix", "$O(V+E)$ space") is written in terms of these two bags. This is the vocabulary of the whole chapter.

5. The bars $|V|$ and $|E|$: how many

Why the topic needs it: space and time costs are numbers, so they depend on counts ($|V|$, $|E|$), not on the abstract bags. $O(V^2)$ is meaningless until $V$ means "a number."

6. Degree and $\mathrm{deg}u$

In the figure of Section 1, dot $2$ touches dots $0$, $1$, and $3$, so $\mathrm{deg}2=3$. Dot $3$ touches only dot $2$, so $\mathrm{deg}3=1$.

Why the topic needs it: the parent's cost "list neighbours of $u$ is $O(\mathrm{deg}u)$" is meaningless unless you know $\mathrm{deg}u$ is "how many neighbours $u$ actually has" — and the $2E$ list-size claim rests entirely on this.

7. Neighbours and the neighbour list adj[u]

In the figure, adj[2] = [0, 1, 3] — dot 2's three neighbours. Notice adj[u] has exactly $\mathrm{deg}u$ items. That's the link between Section 6 and how the list representation stores things.

Why the topic needs it: the adjacency list representation is literally an array of these neighbour lists. Understanding "neighbour" is understanding the list.

8. The grid $A$ and the entry $A[u][v]$

Read it like a battleship board or a seating chart: go down to row $u$, across to column $v$, read the cell. The figure below shows the grid for our 4-dot graph — a $1$ means "edge here," a $0$ means "no edge."

Why the topic needs it: the entire adjacency-matrix representation is "let $A[u][v]=1$ when there's an edge." Every space and time claim about the matrix is a claim about this grid.

9. The counting symbol $\left(\genfrac{}{}{0ex}{}{V}{2}\right)$

Why the $\frac{1}{2}$? Picture picking two dots: the first can be any of $V$, the second any of the remaining $V-1$, giving $V(V-1)$ ordered picks. But $\{0,1\}$ and $\{1,0\}$ are the same unordered pair, so we've double-counted — divide by $2$.

This is the maximum possible number of edges in an undirected graph with no repeats and no self-loops: you can't have more lines than there are distinct pairs to join.

Why the topic needs it: it sets the ceiling $0\le E\le \left(\genfrac{}{}{0ex}{}{V}{2}\right)\approx V^2/2$. That ceiling is what makes the matrix's $V^2$ cells "not crazy" and what defines dense (near the ceiling) vs sparse (far below it) — see Sparse vs Dense Graphs.

10. The growth symbol: $O(\cdot )$

For example $O(V+E)$ means "grows roughly like the number of vertices plus the number of edges." $O(V^2)$ means "grows like the square of the vertex count" — double $V$ and the cost roughly quadruples. Full treatment in Big-O Notation.

Why the topic needs it: the whole comparison — matrix $O(V^2)$ space vs list $O(V+E)$ space — is stated in this language. Without Big-O you cannot even state the trade-off.

11. Sparse vs dense

Why the topic needs it: this single word decides the winner. Sparse → list wins on space. Dense → the list is also $O(V^2)$ and the matrix's $O(1)$ edge check wins. See Sparse vs Dense Graphs.

How these feed the topic

Everything on the left is built in this page; the two boxes K and L are the parent topic Representations, and M is the decision it teaches you to make. These foundations also power Breadth-First Search (BFS), Depth-First Search (DFS), Dijkstra's Algorithm, Floyd-Warshall Algorithm, and the walk-counting fact needs Matrix Multiplication.

Equipment checklist

Hide the right side and test yourself — if any answer is fuzzy, re-read that section before touching the parent note.