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

WHAT we do: just count dots and lines from figure s01.

• (a) Dots $0,1,2,3$ → $V=4$.
• (b) Lines drawn: $\{0,1\},\{0,2\},\{1,2\},\{2,3\}$ → $E=4$.
• (c) Lines touching vertex $2$: to $0$, to $1$, to $3$ → $\mathrm{deg}(2)=3$. (Look at the three cyan lines meeting the amber dot.)
• (d) The lines have no arrowheads, so each is two-way → undirected. ✔

WHAT / WHY: to check an edge in a matrix we simply index the cell — that is the $O(1)$ superpower of the matrix.

• Edge $(0,2)$: read $A[0][2]=0$ → no edge.
• $\mathrm{deg}(1)$: count the $1$s in row 1 → $A[1][0]=1,A[1][2]=1$ → $\mathrm{deg}(1)=2$.
• Symmetry check: $A[0][1]=A[1][0]=1$, $A[1][2]=A[2][1]=1$, and every mirrored pair matches, so $A=A^T$ → undirected. ✔

WHAT we do: for every edge $\{u,v\}$ set both $A[u][v]=1$ and $A[v][u]=1$ (undirected ⇒ symmetric), and push each endpoint into the other's list.

Matrix ($5\times 5$, rows/cols $\mathrm{0..4}$): $A=\left(\begin{array}{ccccc}0& 1& 0& 0& 0\\ 1& 0& 1& 1& 0\\ 0& 1& 0& 0& 0\\ 0& 1& 0& 0& 1\\ 0& 0& 0& 1& 0\end{array}\right)$ Why row 1 has three 1s: vertex $1$ touches $0,2,3$ → columns $0,2,3$.

List:

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

Total list entries $=2E=8$ (each of the $4$ edges appears twice). ✔

WHY these formulas: matrix always allocates one cell per ordered pair → $V^2$. List allocates $V$ headers plus $2E$ endpoint entries (undirected).

• (a) $V^2=50000^2=2.5\times 10^9$ cells.
• (b) $V+2E=50000+2(120000)=50000+240000=290000$ entries.
• (c) List is smaller. Factor $=\frac{2.5\times 10^9}{2.9\times 10^5}\approx 8621$ — the list uses roughly 8600× less memory. Sparse graph → list wins. ✔

BFS choice: BFS repeatedly asks "who are $u$'s neighbours?" and visits each vertex/edge once. In a list that whole sweep costs ${\sum }_u\mathrm{deg}(u)=2E$, so BFS is $O(V+E)$. In a matrix each neighbour scan is $O(V)$, forcing $O(V^2)$. → Use the adjacency list. Same argument holds for Depth-First Search (DFS). ✔

WHY symmetry: for undirected graphs $\{u,v\}$ forces both cells to $1$, so $A=A^T$.

• (a) No. If it were undirected, $A[7][3]$ would also be $1$. The mismatch breaks $A=A^T$.
• (b) It is a directed graph: there is a one-way arrow $3\to 7$ but no arrow $7\to 3$. Directed matrices need not be symmetric. ✔

WHAT we do: set the two costs equal and solve for $E$. $2E=V^2\Rightarrow E=\frac{V^2}{2}.$ But the maximum possible $E$ for a simple undirected graph is $\left(\genfrac{}{}{0ex}{}{V}{2}\right)=\frac{V(V-1)}{2}\approx \frac{V^2}{2}$. So the list's raw entry count only reaches the matrix's cell count at (essentially) maximum density — a complete graph. For everything sparser, $2E<V^2$ and the list stores fewer things. In Big-O terms both are $O(V^2)$ once $E=\Theta (V^2)$, so their space asymptotics tie for dense graphs, and the matrix's $O(1)$ edge check becomes the tie-breaker. ✔

WHY matrix powers: $(A^2)[u][v]={\sum }_{m}A[u][m]A[m][v]$ counts every middle vertex $m$ neighbouring both $u$ and $v$ — i.e. every $2$-step route. Compute $A^2$: $A^2=\left(\begin{array}{ccc}2& 1& 1\\ 1& 2& 1\\ 1& 1& 2\end{array}\right)$

• (a) $(A^2)[0][0]=2$: routes $0\to 1\to 0$ and $0\to 2\to 0$ → 2 walks.
• (b) $(A^2)[0][1]=1$: only route $0\to 2\to 1$ (you can't step $0\to 1\to 1$ since no self-loop) → 1 walk. ✔

Reasoning = access pattern + density.

• (a) Matrix. Floyd–Warshall indexes dist[i][j] inside triple loops and needs $O(1)$ edge weight lookups; $V^2=2.5\times 10^5$ cells is cheap. Its own runtime is $O(V^3)$ so the matrix fits perfectly.
• (b) List. $E\ll V^2$ (very sparse); Dijkstra sweeps each vertex's neighbours, total $O(E\log V)$ with a heap — a matrix would force $O(V^2)$ neighbour scans, a disaster at $V=10^6$.
• (c) List. DFS visits each vertex and edge once → $O(V+E)$ with a list, versus $O(V^2)$ scanning matrix rows. ✔

WHAT / WHY: expand the matrix-product definition and use the meaning of $A$'s entries. $(A^2)[u][u]={\sum }_{m=0}^{V-1}A[u][m]A[m][u].$ Each term $A[u][m]A[m][u]$ equals $1$ exactly when $m$ is a neighbour of $u$ (then $A[u][m]=A[m][u]=1$ by symmetry), and $0$ otherwise. Summing $1$ once per neighbour of $u$ gives the number of neighbours: $(A^2)[u][u]=\#\{m:A[u][m]=1\}=\mathrm{deg}(u).■$ Sanity check against L4.1: triangle vertex $0$ has $\mathrm{deg}(0)=2$, and indeed $(A^2)[0][0]=2$. ✔

• (a) Matrix needs $V^2=6000^2=3.6\times 10^7$ cells. Since $3.6\times 10^7\le 8\times 10^7$, the matrix fits. ✔
• (b) List budget: $V+2E\le 8\times 10^7\Rightarrow 2E\le 8\times 10^7-6000=79,994,000\Rightarrow E\le 39,997,000$. So a list could hold up to about $4.0\times 10^7$ edges — but a simple graph on $6000$ vertices has at most $\left(\genfrac{}{}{0ex}{}{6000}{2}\right)=\frac{6000\cdot 5999}{2}=17,997,000$ edges, so the real cap is $E\le 17,997,000$.
• (c) Rule: if $2E<V^2$, the list stores fewer things (sparse → list); if $E$ is near $\left(\genfrac{}{}{0ex}{}{V}{2}\right)$ (dense) and you need fast edge queries, take the matrix. Here $V$ is small enough that the matrix comfortably fits, so if you need $O(1)$ isEdge the matrix is fine. ✔

1. For undirected $\{u,v\}$, how many matrix cells and how many list entries does it create?
2. Why is BFS $O(V+E)$ with a list but $O(V^2)$ with a matrix?
3. What is $(A^2)[u][u]$ for a simple undirected graph?
4. At what $E$ do $2E$ and $V^2$ meet, and what graph is that?

Answers: 1) two cells ($A[u][v],A[v][u]$) and two list entries. 2) list visits $\sum \mathrm{deg}=2E$ neighbours total; matrix scans $V$ columns per vertex. 3) $\mathrm{deg}(u)$. 4) $E=V^2/2\approx \left(\genfrac{}{}{0ex}{}{V}{2}\right)$ — a complete graph.