# Graph Representations

Computer Science I · Data Structures · https://tryals.app/learn/computer-science-i/graph-representations

## Graph Basics

A **graph** models things and their connections: **vertices** (nodes) joined by **edges**. They represent road maps, social networks, and dependency chains.

Edges can be **directed** (one-way) or **undirected** (mutual), and may carry a **weight** representing distance, cost, or capacity.

| Property | Description |
| --- | --- |
| **Vertices ($V$)** | The nodes being connected |
| **Edges ($E$)** | The connections between nodes |
| **Weight** | Cost, distance, or capacity |

**Common Pitfall:** Using an **adjacency matrix** for a large **sparse** graph. A million-node graph with few edges wastes $O(V^2)$ space on empty cells.

## Memory Trade-offs

Choosing a graph representation is a classic space-time trade-off between two standard structures.

An **adjacency matrix** is a $V \times V$ grid where entry $(i, j)$ records the connection. It allows $O(1)$ edge checking, suiting **dense** graphs.

An **adjacency list** stores each vertex's neighbors. It uses $O(V + E)$ space, suiting **sparse** graphs.

| Representation | Space | Check edge | Best for |
| --- | --- | --- | --- |
| **Adjacency matrix** | $O(V^2)$ | $O(1)$ | Dense graphs |
| **Adjacency list** | $O(V + E)$ | $O(\deg u)$ | Sparse graphs |

## Practice questions

3 of this lesson's 10 practice questions, with answers. The full set is in the app.

### 1. Sort each relationship by the kind of edge that models it.

**Answer:**

- Directed edge: Account A follows account B, but not the other way round, One web page contains a link to another page
- Undirected edge: Two atoms are joined by a chemical bond
- Weighted edge: The road between two towns is 12 kilometres long

**Why:** Direction and weight are independent choices: a relation is one-way or mutual, and separately it may or may not carry a cost, distance or capacity. Modelling a one-way relation as undirected quietly invents connections that do not exist, which is how graph models of social networks go wrong.

Page: https://tryals.app/practice/computer-science-i/graph-representations/sort-each-relationship-by-the-kind-of-edge-that-models-it

### 2. An adjacency list couples memory usage directly to the number of existing connections, whereas a matrix allocates for all potential connections. What follows from this distinction when choosing an architecture for dynamic networks?

A. A matrix outpaces list memory whenever edges exceed vertices
B. The list structure incurs an unacceptable lookup penalty in dense networks
C. List memory scales with edge growth instead of worst-case capacity
D. A matrix avoids wasting space on non-existent connections in sparse graphs

**Answer:** C. List memory scales with edge growth instead of worst-case capacity

**Why:** Matrix sizes depend strictly on vertex count regardless of sparsity, while lists allocate only for real edges. At extreme density, list node overhead can surpass simple tabular arrays, but edge lookup costs remain bounded by vertex degree rather than whole-graph scale.

Page: https://tryals.app/practice/computer-science-i/graph-representations/an-adjacency-list-couples-memory-usage-directly-to-the-number-of

### 3. Why does allocating an adjacency matrix for a sparse network of one million members cause a critical memory issue?

A. Because adjacency lists are faster than matrices for every operation, so the matrix is never the right choice.
B. Because adjacency matrices cannot represent undirected graphs, which is what a social network is.
C. Because the matrix needs a trillion cells, almost all of them zero.
D. Because a matrix cannot store more than a few thousand vertices for technical reasons.

**Answer:** C. Because the matrix needs a trillion cells, almost all of them zero.

**Why:** The arithmetic settles it: 10¹² cells to record a few hundred million edges, about 0.03% non-zero. Lists store only what exists, which for a sparse graph is the difference between infeasible and routine. The cost is real, 'are A and B connected?' becomes a scan of A's list, so density decides, and real-world networks are almost always sparse.

Page: https://tryals.app/practice/computer-science-i/graph-representations/why-does-allocating-an-adjacency-matrix-for-a-sparse-network-of-one