Graph Representations
This file covers the data structure aspects of graphs — how to store and access graph data efficiently. Graph algorithms are covered in topic 09.
Representations
Adjacency Matrix
A 2D array A where A[i][j] = 1 (or weight) if edge (i, j) exists.
// Unweighted graph
adj_matrix ← n x n matrix of false values
// Weighted graph
adj_matrix ← n x n matrix of INFINITY values
| Operation | Time |
|---|---|
| Check edge (u, v) | O(1) |
| List neighbors of u | O(V) |
| Add edge | O(1) |
| Remove edge | O(1) |
| Space | O(V²) |
Best for: Dense graphs (E ≈ V²), matrix-based algorithms (Floyd-Warshall, matrix exponentiation), small graphs.
Matrix properties: A^k[i][j] = number of walks of length k from i to j. Eigenvalues reveal graph structure (spectral graph theory).
Adjacency List
Each vertex stores a list of its neighbors (and edge weights).
// Unweighted
adj_list ← array of n empty lists
// Weighted
adj_list ← array of n empty lists // each entry is (neighbor, weight)
// Add edge u → v with weight w
APPEND (v, w) TO adj_list[u]
| Operation | Time |
|---|---|
| Check edge (u, v) | O(deg(u)) |
| List neighbors of u | O(deg(u)) |
| Add edge | O(1) amortized |
| Remove edge | O(deg(u)) |
| Space | O(V + E) |
Best for: Sparse graphs (E ≪ V²), BFS/DFS, most graph algorithms. The default choice.
Edge List
Simply a list of all edges.
STRUCTURE Edge
from : integer
to : integer
weight : real number
edges ← empty list of Edge
| Operation | Time |
|---|---|
| Check edge (u, v) | O(E) |
| List neighbors of u | O(E) |
| Add edge | O(1) |
| Sort edges | O(E log E) |
| Space | O(E) |
Best for: Kruskal's algorithm (sort edges by weight), input/output, simple storage.
Incidence Matrix
V × E matrix B where B[v][e] = 1 if vertex v is an endpoint of edge e. For directed graphs: B[v][e] = -1 (tail), +1 (head).
Space: O(V × E). Rarely used in practice.
Theoretical use: The Laplacian L = BB^T (for directed incidence matrix).
Choosing a Representation
| Criterion | Adjacency Matrix | Adjacency List |
|---|---|---|
| Dense graph | Best | Wastes pointers |
| Sparse graph | Wastes memory | Best |
| Edge existence check | O(1) | O(deg) |
| Iterate all edges | O(V²) | O(V + E) |
| Add vertex | O(V) (resize) | O(1) |
| Memory | O(V²) | O(V + E) |
| Cache behavior | Good (contiguous) | Varies |
| Matrix algorithms | Natural | Requires conversion |
Rule of thumb: Use adjacency list unless you need O(1) edge queries or the graph is dense.
Directed vs Undirected
Undirected: Edge {u, v} stored in both adj[u] and adj[v]. Or in the upper triangle of the adjacency matrix.
Directed: Edge (u, v) stored only in adj[u] (out-edges). For algorithms needing in-edges, maintain a reverse adjacency list too.
Weighted Graphs
Store weights alongside edges:
- Adjacency matrix: A[i][j] = weight (use ∞ or sentinel for no edge)
- Adjacency list: Vec<(neighbor, weight)>
- Edge list: Edge struct with weight field
Implicit Graphs
Some graphs are too large to store explicitly. Instead, generate neighbors on the fly.
Examples:
- State space search: States are nodes, transitions are edges. Generated during BFS/DFS.
- Game trees: Board positions as nodes, moves as edges.
- Grid graphs: 2D/3D grids where neighbors are computed from coordinates.
- Permutation graphs: Permutations as nodes, swaps as edges.
// Implicit graph: 2D grid
FUNCTION NEIGHBORS(r, c, rows, cols)
directions ← [(0,1), (0,-1), (1,0), (-1,0)]
result ← empty list
FOR EACH (dr, dc) IN directions DO
nr ← r + dr
nc ← c + dc
IF nr ≥ 0 AND nr < rows AND nc ≥ 0 AND nc < cols THEN
APPEND (nr, nc) TO result
RETURN result
Compressed Representations
CSR (Compressed Sparse Row)
Efficient for static graphs (no edge insertions). Used in high-performance graph libraries.
row_ptr: [0, 2, 5, 7, 9] // Start index of each vertex's edges
col_idx: [1, 3, 0, 2, 3, 1, 3, 0, 2] // Neighbor lists concatenated
weights: [4, 2, 4, 1, 5, 1, 3, 2, 3] // Edge weights (optional)
Vertex 0's neighbors: col_idx[row_ptr[0]..row_ptr[1]] = col_idx[0..2] = [1, 3].
Space: O(V + E). Very compact. Excellent cache locality for sequential access.
Used in: Graph analytics frameworks (GraphBLAS, Ligra), scientific computing, GPU graph processing.
Sparse vs Dense Tradeoffs
| V = 1000 | Adjacency Matrix | Adjacency List (avg degree 10) |
|---|---|---|
| Memory | 1,000,000 entries | 10,000 entries |
| Edge check | O(1) | O(10) |
| All edges | O(1,000,000) | O(10,000) |
For social networks (V = 10⁹, avg degree = 100): Adjacency matrix would require 10¹⁸ entries (exabytes!). Adjacency list: ~10¹¹ entries (terabytes — large but feasible).
Applications in CS
- Social networks: Adjacency list or CSR for large-scale graph storage. Graph databases (Neo4j) for flexible querying.
- Maps/Navigation: Adjacency list with edge weights (distance, time). Contraction hierarchies preprocess the graph for fast queries.
- Web crawling: Implicit graph. URLs are nodes, hyperlinks are edges.
- Compilers: Control flow graph, data dependency graph, call graph — all represented as directed graphs.
- Networking: Network topology as a graph. Routing tables derived from graph algorithms.
- Recommendation systems: User-item bipartite graph. Collaborative filtering on graph structure.
- Knowledge graphs: Entity-relationship graphs. RDF triples as edges in a directed labeled graph.