How do you represent a graph: adjacency list vs adjacency matrix?

Question

Accepted Answer

A **graph** is a set of **vertices** connected by **edges**. The two standard representations are the **adjacency list** (each vertex stores its neighbors) and the **adjacency matrix** (a V×V grid of booleans). The choice depends on graph **density**.

## The two forms

```text
Graph:  0 - 1
        |   |
        2 - 3

Adjacency list:          Adjacency matrix:
0: [1, 2]                    0 1 2 3
1: [0, 3]                 0 [0 1 1 0]
2: [0, 3]                 1 [1 0 0 1]
3: [1, 2]                 2 [1 0 0 1]
                          3 [0 1 1 0]
```

## Code

```python
# Adjacency list (dict of lists) — preferred for sparse graphs
adj = {0: [1, 2], 1: [0, 3], 2: [0, 3], 3: [1, 2]}
neighbors = adj[1]            # O(1) to get a vertex's neighbors

# Adjacency matrix
matrix = [[0]*4 for _ in range(4)]
matrix[0][1] = matrix[1][0] = 1
has_edge = matrix[0][1] == 1  # O(1) edge lookup
```

## Comparison (V vertices, E edges)

| | Adjacency list | Adjacency matrix |
|---|---|---|
| Space | O(V + E) | O(V²) |
| Edge exists? | O(degree) | O(1) |
| Iterate neighbors | O(degree) | O(V) |
| Best for | sparse graphs | dense graphs |

## Why it matters

Most real-world graphs (social networks, road maps, dependency graphs) are **sparse**, so adjacency lists save enormous space and speed up traversals like BFS/DFS.

Knowing the trade-off lets you pick the representation that keeps your graph algorithms efficient instead of accidentally using O(V²) memory.

	Adjacency list	Adjacency matrix
Space	O(V + E)	O(V²)
Edge exists?	O(degree)	O(1)
Iterate neighbors	O(degree)	O(V)
Best for	sparse graphs	dense graphs