---
title: "Graph Representation"
description: "Adjacency list vs matrix, edges, and degree — how a graph becomes data."
source: https://vizlearn.app/algorithms/data-structures/graph-representation
---

# Graph Representation

Graph representation turns vertices and edges into data a program can store and query. An adjacency list keeps one neighbor row per vertex and uses O(V + E) space. An adjacency matrix reserves a V by V grid, spends O(V²) space, and answers `has_edge(u, v)` with one indexed lookup.

Think of the list as an address book: open vertex `u` and read only the neighbors it actually has. The matrix is a seating chart with a box for every possible pair, including the pairs that never meet. The empty boxes cost space; the fixed coordinates buy speed.

## Graph representation trades space for lookup speed

The lesson uses a simple undirected graph. "Simple" means no parallel edges and no self-loops. "Undirected" means edge `u-v` has no preferred direction, so both representations must store it symmetrically.

In an adjacency list, edge `u-v` performs two appends: put `v` in `adj[u]`, then put `u` in `adj[v]`. Each undirected edge therefore contributes two neighbor entries. Across the whole graph, the rows hold exactly `2E` entries, plus one row head for each of the `V` vertices.

In an adjacency matrix, the same edge sets two cells: `matrix[u][v] = 1` and `matrix[v][u] = 1`. The two ones mirror each other across the main diagonal. A zero means no edge. Because this lesson excludes self-loops, the diagonal stays zero.

That symmetry is the invariant. If the list stores both directions but the matrix writes only one cell, the structures describe different graphs. If the list appends only one direction, it has quietly become a directed graph while the picture still claims otherwise.

The two structures make different operations cheap. A list can report `degree(u)` from the length of row `adj[u]`. To test whether `u-v` exists, however, it scans that row until it finds `v` or reaches the end. A matrix does the reverse trade: degree requires summing an entire row, but edge membership is the single cell `matrix[u][v]`.

## Graph representation step by step

The default graph has vertices `0` through `5` and five edges, processed in this order:

`0-1`, `0-2`, `1-3`, `2-3`, `3-4`

Vertex `5` is isolated. That is deliberate; a graph representation should not need special pleading to store a vertex with degree zero.

1. Allocate six empty list rows and a 6 by 6 matrix of zeros.
2. Encode edge `0-1`. Append `1` to `adj[0]`, append `0` to `adj[1]`, then set matrix cells `[0][1]` and `[1][0]` to `1`.
3. Encode edge `0-2` the same way. Rows `adj[0]` and `adj[2]` gain mirror entries, and cells `[0][2]` and `[2][0]` become `1`.
4. Repeat the three writes for `1-3`, `2-3`, and `3-4`. No write ever touches vertex `5`.
5. The finished adjacency list is `0:[1,2]`, `1:[0,3]`, `2:[0,3]`, `3:[1,2,4]`, `4:[3]`, `5:[]`. It contains ten neighbor entries: exactly `2E = 10`.
6. The matrix contains 36 cells because `V² = 6² = 36`. Its row for vertex `3` is `[0,1,1,0,1,0]`, matching neighbors `1`, `2`, and `4` from the list.
7. Compute `degree(3)`. The list reads `len(adj[3]) = 3`. The matrix sums row `3`, also obtaining `3`, but it inspects all six cells to do so.
8. Ask `has_edge(3, 5)`. The list compares `1` with `5`, then `2`, then `4`; the row ends after three probes, so the answer is `False`.
9. The matrix reads `matrix[3][5]`. That one cell is `0`, so it returns the same `False` answer in one lookup.

On the canvas, the source edge stays visible while its list entries and symmetric matrix cells light up. During the query, the list cursor walks neighbor by neighbor; the matrix guides cross at one cell. The motion is not decoration. It is the cost model made visible.

## Time and space complexity

Let `V` be the number of vertices, `E` the number of undirected edges, and `degree(u)` the number of neighbors of vertex `u`.

Let the workload choose. If your program asks millions of arbitrary edge-membership questions, a matrix may earn its space. If it mostly walks the neighbors that exist, an adjacency list avoids scanning a desert of zeros.

| Operation | Adjacency list | Adjacency matrix |
|---|---:|---:|
| Space | O(V + E) | O(V²) |
| Add undirected edge | O(1) amortized | O(1) |
| `has_edge(u, v)` | O(degree(u)) | O(1) |
| `degree(u)` | O(1) from row length | O(V) from a row sum |

The list wins the usual sparse-graph argument because `E` is far smaller than `V²`. The default needs six row heads and ten neighbor entries, while the matrix reserves 36 cells.

Dense K5 is the useful correction. A complete five-vertex graph has ten edges, so the list's logical term count is `V + 2E = 5 + 20 = 25`, exactly the matrix's `V² = 25` cells. Those counts are not byte measurements; real arrays, pointers, and row objects have different overhead. They do show why the list's asymptotic space advantage disappears when `E = Θ(V²)`.

## Edge cases

- **Singleton graph:** one vertex, no edges. Its list row is empty, its 1 by 1 matrix contains zero, and `degree(0) = 0`.
- **Isolated vertex:** vertex `5` in the default has a real row and matrix row even though both contain no neighbors.
- **Absent edge:** `has_edge(3, 5)` returning `False` is normal data, not an error condition.
- **Dense graph:** Dense K5 removes the list's sparse-space advantage and makes a late list hit scan four neighbors.
- **Self-loops and parallel edges:** this lesson excludes both. Supporting them requires an explicit convention about diagonal cells and duplicate list entries.

## Common mistakes

- **Writing only one list direction.** For an undirected edge `u-v`, both `adj[u]` and `adj[v]` must change.
- **Writing only one matrix cell.** An undirected adjacency matrix is symmetric, so `[u][v]` and `[v][u]` must agree.
- **Claiming matrix space is O(E).** The grid reserves `V²` cells even when almost every cell is zero.
- **Scanning every vertex for a list query.** `has_edge(u, v)` scans only `adj[u]`, so its bound is O(degree(u)), not automatically O(V + E).
- **Treating logical entries as bytes.** `V + 2E` and `V²` explain growth rates. They do not claim that one list entry occupies the same memory as one matrix cell.