4 min read
On this page

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.