Graph Representation

A graph is one of the most powerful and versatile data structures in computer science: it models pairwise relationships between objects — cities and roads, users and friendships, tasks and dependencies.

Formally, a graph G = (V, E) is a set of vertices V and a set of edges E, where each edge connects two vertices. Choosing how to store those edges is a systems decision: it sets the space cost of the whole program and the asymptotic cost of every graph algorithm you run on top of it.

Key Properties

These choices constrain the representation: directed graphs need asymmetric storage, weighted graphs store a cost per edge, and large graphs push you toward sparse-friendly formats.

The Three Standard Representations

All three forms below encode the same graph — vertices A–E with edges A–B, A–D, B–C, C–E, D–E:

        A
       / \
      B   D
       \   \
        C—E

Adjacency matrix:           Adjacency list:        Edge list:
     A  B  C  D  E          A → [B, D]            (A, B)
A   [0, 1, 0, 1, 0]         B → [A, C]            (A, D)
B   [1, 0, 1, 0, 0]         C → [B, E]            (B, C)
C   [0, 1, 0, 0, 1]         D → [A, E]            (C, E)
D   [1, 0, 0, 0, 1]         E → [C, D]            (D, E)
E   [0, 0, 1, 1, 0]

Adjacency Matrix

An N×N matrix where matrix[u][v] is the weight (or 1) if edge (u, v) exists, else 0 (or ∞).

• Space: O(V²) — allocated up front regardless of how many edges actually exist.
• Check edge (u, v): O(1) — a single array index.
• Iterate neighbors: O(V) — must scan the entire row even if it holds two entries.
• Best for: dense graphs, small V, or algorithms that hammer “is there an edge?” (Floyd–Warshall, transitive closure).

Adjacency List

Each vertex maps to a list (or array) of its neighbors, plus the weight when needed.

• Space: O(V + E) — proportional to the edges that actually exist.
• Check edge (u, v): O(degree(u)) — must scan u’s list.
• Iterate neighbors: O(degree(u)) — exactly the neighbors, nothing wasted.
• Best for: sparse graphs — which is most real-world graphs (a city map has ~4 neighbors per intersection, not V).

The iteration cost is the decisive point: BFS, DFS, and Dijkstra all spend their time iterating neighbors, so on a sparse graph the adjacency list turns O(V²) scanning into O(V + E) total work.

Edge List

A flat list of (u, v, weight) triples.

• Space: O(E) — the smallest possible, no structure beyond the edges.
• Check edge / iterate neighbors: O(E) scan of the whole list.
• Best for: algorithms that stream all edges once (Kruskal’s MST), or as a compact interchange format.

Choosing a Representation

Weighted and Directed Variants

• Weighted: the matrix stores the weight (use ∞ for “no edge”); the adjacency list stores (neighbor, weight) pairs; the edge list already carries the third field.
• Directed: the matrix is no longer symmetric (matrix[u][v] ≠ matrix[v][u]); an adjacency list stores only outgoing edges, so iterating in-edges costs a full scan unless you keep a reversed list; edge lists distinguish source and target.
• Practical trick: many systems store a forward adjacency list plus a reversed one to make reverse traversals cheap — common in compiler dependency graphs.

Implicit Representations

Not every graph needs materialized storage. An implicit graph computes neighbors on the fly from coordinates or rules: a Sudoku cell’s neighbors from its (row, col) position, a knight’s moves from a chess square, a pathfinding grid’s 4 or 8 neighbors from coordinate arithmetic.

Implicit graphs trade a little recomputation for zero storage — ideal for state spaces too large to enumerate (a puzzle’s search space can be 10²⁰ states, none of which you can afford to store).

Worked Example

Route planning on a road map with 10,000 intersections and ~3 road segments each, running Dijkstra:

Adjacency list:   storage ≈ 30,000 entries
Adjacency matrix: storage ≈ 10⁸ cells → 400 MB at 4 bytes each

Dijkstra iterates neighbors constantly. The matrix’s O(1) edge lookup is worthless if each neighbor pass scans a 10,000-cell row — that is O(V²) work. The adjacency list stores exactly the roads that exist, so iteration costs what the map actually contains — three orders of magnitude less, in both space and time. The matrix wins only when V is small and the graph dense.

Practice Trajectory

1. Build all three representations for the same 6-vertex graph by hand and confirm they encode identical edges.
2. Implement BFS twice — once over an adjacency list, once over a matrix — and compare total steps on a sparse 50-node graph.
3. Measure checkEdge cost in each form and record when the matrix’s O(1) actually matters.
4. Model a directed dependency graph with a reversed adjacency list and run topological sort on it.
5. Implement an implicit grid graph (no stored edges) and count neighbors generated while running BFS on a 100×100 board.

When It’s the Right Tool