Graphs: Representations

A graph G = (V, E) consists of a set of vertices (also called nodes) V and a set of edges E. Each edge connects a pair of vertices.

In an undirected graph, edges are unordered pairs: edge {u, v} = {v, u}. Think of a friendship network — if Alice is friends with Bob, Bob is friends with Alice. The edge has no arrow.

In a directed graph (digraph), edges are ordered pairs: edge (u, v) means there is an arrow from u to v but not necessarily from v to u. Think of Twitter follows, or one-way streets.

In a weighted graph, each edge carries a numerical label called its weight (or cost). Road networks are weighted by distance or travel time; communication networks by bandwidth or latency.

Key vocabulary you must know cold:

• Degree of vertex v (undirected): number of edges incident to v. Notation: deg(v).
• In-degree / out-degree (directed): number of edges pointing into / out of v.
• Adjacency: vertex u is adjacent to v (or u is a neighbor of v) if edge (u,v) or {u,v} exists.
• Path: a sequence of vertices v₀, v₁, ..., vₖ where each consecutive pair is an edge.
• Sparse graph: E = O(V) — few edges relative to vertices. Road networks, dependency graphs.
• Dense graph: E = Θ(V²) — many edges. Complete graphs, some social networks.

The fundamental identity for undirected graphs: Σ deg(v) = 2|E| (the Handshaking Lemma). Each edge contributes to exactly two degree counts. This seemingly simple fact underpins many analyses.

# Python: basic graph vocabulary
V = {0, 1, 2, 3}                    # vertex set
E = {(0,1), (1,2), (2,3), (0,3)}    # undirected edge set

# Handshaking Lemma: sum of degrees = 2 * |E|
deg = {v: 0 for v in V}
for u, v in E:
    deg[u] += 1
    deg[v] += 1
assert sum(deg.values()) == 2 * len(E)  # always true for undirected

The adjacency matrix for a graph G = (V, E) with |V| = n is an n × n matrix A where:

• Unweighted, undirected: A[i][j] = 1 if edge {i,j} exists, else 0. The matrix is symmetric: A = Aᵀ.
• Unweighted, directed: A[i][j] = 1 if directed edge (i→j) exists, else 0. Not necessarily symmetric.
• Weighted: A[i][j] = w(i,j) if edge exists, else 0 or ∞ (depending on convention). For shortest-paths, ∞ for missing edges and 0 on the diagonal is standard.

Space: Θ(n²) always, regardless of |E|. For n = 1,000,000 vertices, this is 10¹² bits ≈ 125 GB. Clearly impractical for large sparse graphs.

Key operations:

• Edge lookup A[u][v]: O(1) — just array indexing.
• Iterate all neighbors of u: O(n) — must scan all n columns, even for sparse graphs.
• Add/remove edge: O(1).

Why the symmetry matters: for undirected graphs, you can store only the upper triangle, halving space. But you still allocate O(n²) entries.

The beauty of matrix algebra: the entry (A^k)[i][j] counts the number of walks of length k from i to j. This is genuinely magical — matrix exponentiation on the adjacency matrix becomes a path-counting algorithm. This algebraic structure is why adjacency matrices appear in spectral graph theory, Google's PageRank formulation, and quantum computing.

Cache behavior: adjacency matrices are stored row-major in most languages. Iterating over neighbors of u (A[u][0], A[u][1], ..., A[u][n-1]) hits consecutive memory addresses — excellent spatial locality. This sometimes makes the O(n) neighbor scan competitive with the O(degree) list scan in practice, especially for dense graphs.

# Adjacency matrix for directed weighted graph
import math

INF = math.inf
n = 4  # vertices 0..3

# Initialize: 0 on diagonal, INF elsewhere
A = [[INF]*n for _ in range(n)]
for i in range(n): A[i][i] = 0

# Add directed weighted edge u->v with weight w
def add_edge(u, v, w):
    A[u][v] = w

add_edge(0, 1, 5)
add_edge(0, 3, 2)
add_edge(1, 2, 3)
add_edge(3, 1, 1)

# Edge lookup: O(1)
print(A[0][1])  # 5
print(A[2][0])  # inf (no edge)

# Iterate neighbors of vertex 0: O(n)
for v in range(n):
    if A[0][v] != INF and v != 0:
        print(f"0 -> {v}, weight={A[0][v]}")

The adjacency list represents G = (V, E) as an array (or dictionary) of n lists, one per vertex. adj[u] contains all vertices v such that edge (u, v) exists (for directed graphs) or {u, v} exists (for undirected).

For weighted graphs, each entry in adj[u] is a (vertex, weight) pair.

Space: Θ(V + E). For a sparse graph where E = O(V), this is Θ(V) — astronomically better than Θ(V²).

Key operations:

• Edge lookup (u, v): O(degree(u)) in the worst case — must scan u's list. For a sparse graph where degree(u) is small (say, constant or O(log n)), this is effectively O(1) in practice but provably not O(1) in the worst case.
• Iterate all neighbors of u: O(degree(u)) — exactly proportional to work done.
• Add edge: O(1) amortized (append to list).
• Remove edge: O(degree(u)) — must find and remove from list.

Why 'iterate neighbors in O(degree)' is critical: Consider BFS on a sparse graph. With an adjacency list, the total work across all neighbor iterations is Σ_u degree(u) = 2E = O(E). BFS is O(V + E). With an adjacency matrix, even though you visit each edge once, you scan all n columns for each vertex: O(n) per vertex, O(V²) total. BFS becomes O(V²), wiping out the benefit.

Implementations: In Python, a defaultdict(list) is idiomatic. In C++, vector<vector<pair<int,int>>> is standard for competitive programming. In production, sorted arrays or hash sets per vertex enable O(log degree) or O(1) expected edge lookup respectively.

The tradeoff visualized: imagine a 1-million-vertex road network where each intersection has on average 3 roads. Adjacency list: ~3 million entries total (V + E). Adjacency matrix: 1 trillion entries. The list is not just better — it makes the problem tractable.

from collections import defaultdict

class Graph:
    """Directed weighted graph via adjacency list."""
    def __init__(self):
        self.adj = defaultdict(list)  # u -> [(v, w), ...]
        self.V = set()

    def add_edge(self, u, v, w=1):
        self.adj[u].append((v, w))
        self.V.update([u, v])

    def neighbors(self, u):  # O(degree(u)) to iterate
        return self.adj[u]

    def has_edge(self, u, v):  # O(degree(u))
        return any(nbr == v for nbr, _ in self.adj[u])

g = Graph()
g.add_edge(0, 1, 5)
g.add_edge(0, 3, 2)
g.add_edge(1, 2, 3)
g.add_edge(3, 1, 1)

for v, w in g.neighbors(0):
    print(f"0 -> {v}, weight={w}")
# 0 -> 1, weight=5
# 0 -> 3, weight=2

Let us be precise. Let V = |V| vertices and E = |E| edges.

The key insight is when edges are rare vs. plentiful. Define the density of a graph as α = E / V². Sparse means α ≈ 0; dense means α ≈ 1.

• When α ≈ 1 (dense), E = Θ(V²), so V + E = Θ(V²). The two representations have the same asymptotic space. Now the constant factor matters: matrix has better cache behavior for neighbor iteration, so it can win.
• When α ≈ 0 (sparse), E = O(V), so V + E = O(V). The matrix wastes Θ(V²) space storing zeros. List dominates overwhelmingly.

The crossover point: use adjacency matrix when E = Ω(V²/log V) approximately, or when O(1) edge lookup is critical for correctness (e.g., Floyd-Warshall, or detecting multi-edges).

A concrete example: Floyd-Warshall all-pairs shortest paths. The algorithm is inherently O(V³) and accesses A[i][k] and A[k][j] in nested loops. An adjacency matrix allows these O(1) lookups. Reimplementing it with adjacency lists requires a hash map lookup per 'edge check', adding log factors or hash overhead. Here, the matrix is the right choice — and the O(V²) space is unavoidable because the output (all-pairs distances) is itself an O(V²) matrix.

Real-world implication: scipy.sparse, NetworkX, and PyTorch Geometric all default to sparse list-style representations (CSR, COO) for graphs, because real-world graphs (web, social, molecular) are almost always sparse.

# Comparing space usage empirically
import sys

def adj_matrix_space(V):
    # V x V matrix of Python ints
    mat = [[0]*V for _ in range(V)]
    return sys.getsizeof(mat) + V * sys.getsizeof(mat[0])

def adj_list_space(V, E_list):
    adj = [[] for _ in range(V)]
    for u, v in E_list:
        adj[u].append(v)
    return sys.getsizeof(adj) + sum(sys.getsizeof(adj[i]) for i in range(V))

V = 1000
# Sparse: each vertex has ~2 edges
E_sparse = [(i, (i+1) % V) for i in range(V)] + [(i, (i+2) % V) for i in range(V)]

matrix_bytes = adj_matrix_space(V)
list_bytes   = adj_list_space(V, E_sparse)
print(f"Matrix: {matrix_bytes:,} bytes for V={V}")
print(f"List:   {list_bytes:,} bytes for V={V}, E={len(E_sparse)}")
# Matrix: ~8,072,000 bytes
# List:   ~     ~56,000 bytes  (143x smaller for sparse)

Undirected graphs require storing each edge once logically, but the two representations handle this differently:

• Matrix: A[u][v] = A[v][u] = 1. You store 2 entries per edge. The matrix is always symmetric. You can optimize by storing only the upper triangle (n(n-1)/2 entries instead of n²), but standard implementations use the full matrix for simplicity.
• List: For each edge {u, v}, you add v to adj[u] and u to adj[v]. Total entries: 2E. This is the standard convention in undirected graph implementations.

Directed graphs are naturally asymmetric:

• Matrix: A[u][v] = 1 means u→v. A[v][u] = 0 means no edge back. No symmetry.
• List: adj[u] contains all vertices v with edge u→v. adj[v] does not contain u unless there is a separate v→u edge.

A common bug: forgetting to add both directions for undirected graphs. If you only add v to adj[u] but not u to adj[v], your 'undirected' graph behaves like a directed one. BFS/DFS will fail to traverse correctly.

In-degree in directed graphs: with an adjacency list indexed by source, computing in-degree(v) requires scanning all adjacency lists (O(V + E)). Alternatively, maintain a separate reverse adjacency list radj[v] = all u with edge u→v. This is standard in algorithms like Kosaraju's SCC that need to traverse edges backwards.

Self-loops and multi-edges: A self-loop is an edge (v, v). The matrix handles this with A[v][v] ≠ 0; lists append v to adj[v]. Multi-edges (multiple edges between same pair) cannot be represented in an adjacency matrix (it would just overwrite), but adjacency lists naturally support them by having duplicate entries.

# Undirected graph: both directions must be added
def build_undirected(V, edges):
    adj = [[] for _ in range(V)]
    for u, v in edges:
        adj[u].append(v)
        adj[v].append(u)   # <-- CRITICAL: must add both
    return adj

# Directed graph: only one direction per edge
def build_directed(V, edges):
    adj  = [[] for _ in range(V)]   # forward
    radj = [[] for _ in range(V)]   # backward / transpose
    for u, v in edges:
        adj[u].append(v)
        radj[v].append(u)            # for in-degree / reverse traversal
    return adj, radj

edges = [(0,1),(1,2),(2,3),(3,0),(0,2)]
adj_u = build_undirected(4, edges)
adj_d, radj_d = build_directed(4, edges)

print("Undirected adj[0]:", adj_u[0])   # [1, 3, 2]
print("Directed   adj[0]:", adj_d[0])   # [1, 2]
print("In-edges of 2:",     radj_d[2])  # [1, 0]

Many real graphs carry data on edges: road distances, network bandwidths, pipe capacities, probabilities of transition. The weight is the most common attribute, but in general you might need labels, capacities, or even multiple attributes per edge.

Weighted adjacency matrix: Replace 0/1 with the weight. A[u][v] = w if edge exists, ∞ (or 0, depending on context) if no edge. The standard for shortest-paths algorithms (Dijkstra, Bellman-Ford, Floyd-Warshall) is:

• A[u][u] = 0 (distance from vertex to itself is 0)
• A[u][v] = ∞ if no edge (you can't reach v from u directly)
• A[u][v] = w(u,v) > 0 if edge exists

Weighted adjacency list: Each entry in adj[u] is a pair (v, weight). In C++, vector<pair<int,int>> per vertex is idiomatic. In Python, list of tuples.

Edge objects: For complex graphs with many attributes, some implementations store a list of Edge objects separately and put edge indices (not weights) in the adjacency list. This allows O(1) access to all attributes of an edge given its index.

Practical example — Dijkstra's algorithm: The priority queue extracts (distance, vertex) pairs. To relax edges from u, we iterate adj[u] in O(degree(u)) time and for each neighbor v check if dist[u] + w(u,v) < dist[v]. This O(degree(u)) neighbor iteration per extraction is what makes Dijkstra O((V+E) log V) with a binary heap — only possible because adjacency lists give us exactly the neighbors we need without wading through non-edges.

Negative weights: Dijkstra requires non-negative weights. Bellman-Ford handles negative weights (but not negative cycles) with the same adjacency list structure. The representation is identical; only the algorithm changes.

// C++: weighted directed graph for Dijkstra
#include <vector>
#include <queue>
#include <climits>
using namespace std;

const int INF = INT_MAX;

vector<int> dijkstra(int src, int V,
    vector<vector<pair<int,int>>>& adj) {
    // adj[u] = {(v, weight), ...}
    vector<int> dist(V, INF);
    priority_queue<pair<int,int>,
        vector<pair<int,int>>, greater<>> pq;

    dist[src] = 0;
    pq.push({0, src});

    while (!pq.empty()) {
        auto [d, u] = pq.top(); pq.pop();
        if (d > dist[u]) continue; // stale entry

        for (auto [v, w] : adj[u]) {  // O(degree(u))
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                pq.push({dist[v], v});
            }
        }
    }
    return dist;
}

When you need memory efficiency and cache performance at scale — as in Google's PageRank, GPU graph neural networks, or scipy.sparse — neither a naive adjacency matrix nor a Python list-of-lists is adequate. The Compressed Sparse Row (CSR) format is the standard solution.

CSR stores a sparse graph in three arrays:

1. data[] (length E): the edge weights (or 1s for unweighted). Edges are listed row by row (source vertex by source vertex).
2. indices[] (length E): the destination vertex of each edge, in the same order as data.
3. indptr[] (length V+1): indptr[u] is the index into data/indices where vertex u's edges begin. indptr[u+1] is where they end. Neighbors of u are indices[indptr[u]:indptr[u+1]].

This packs everything into three contiguous arrays. Neighbor iteration for vertex u — which in a list-of-lists chases two pointers (outer list → inner list) — now accesses a contiguous slice of indices. This is critical for cache performance at scale.

Space: exactly 2E integers plus V+1 integers = O(V + E). Same asymptotic as adjacency list, but much better constant factor due to contiguous allocation.

Why it matters: scipy.sparse, PyTorch Geometric, and DGL all use CSR or its transpose CSC (Compressed Sparse Column) internally. When you call networkx.to_scipy_sparse_array(G), you get CSR. Understanding CSR means you understand the memory layout underlying most production graph algorithms.

The tradeoff: CSR is excellent for static graphs (fixed V and E). Adding/removing edges requires rebuilding the arrays. For dynamic graphs, edge list or hash-map-based adjacency lists are more appropriate.

import numpy as np

def build_csr(V, edges, weights=None):
    """Build CSR from edge list (directed graph)."""
    if weights is None:
        weights = [1] * len(edges)

    # Sort edges by source vertex
    sorted_edges = sorted(zip(edges, weights), key=lambda x: x[0][0])

    data    = np.array([w    for (_,w) in sorted_edges], dtype=np.float32)
    indices = np.array([v    for ((u,v),_) in sorted_edges], dtype=np.int32)

    # Build indptr: indptr[u] = start index of u's edges
    indptr = np.zeros(V + 1, dtype=np.int32)
    for (u, v), w in sorted_edges:
        indptr[u + 1] += 1
    np.cumsum(indptr, out=indptr)  # prefix sum

    return data, indices, indptr

def neighbors_csr(u, indices, indptr):
    """O(degree(u)), fully contiguous memory."""
    return indices[indptr[u]:indptr[u+1]]

edges = [(0,1),(0,3),(1,2),(3,1)]
data, idx, ptr = build_csr(4, edges)
print("Neighbors of 0:", neighbors_csr(0, idx, ptr))  # [1 3]
print("Neighbors of 3:", neighbors_csr(3, idx, ptr))  # [1]

A profound insight: many graphs are too large to store explicitly, but you can still run graph algorithms on them by computing the neighbor function on the fly.

An implicit graph (also called a virtual graph or state space graph) represents vertices as states and edges as transitions. You never allocate an adjacency list or matrix. Instead, you implement a function neighbors(state) -> [state] that computes adjacent states dynamically.

Examples:

• Rubik's Cube: each state is a cube configuration (∼4.3 × 10¹⁹ states). Edges connect states that differ by one twist. BFS on this implicit graph finds the minimum number of moves.
• Word Ladder (classic LeetCode): vertices are words, edges connect words differing by one letter. The 'adjacency list' for "COLD" is computed by trying all single-letter substitutions.
• Sliding puzzle (15-puzzle): states are board configurations, edges are valid tile slides. A* search (a heuristic BFS/Dijkstra) finds the solution.
• Grid graphs: in maze-solving and pathfinding (A* in games), the graph is an n×m grid. neighbors((r,c)) returns up/down/left/right neighbors within bounds. No matrix needed — the grid is the adjacency structure.

This idea is critical in AI (search as graph traversal), competitive programming, and systems (e.g., state-machine reachability). The lesson: 'graph representation' is not just about data structures — it is about the interface that algorithms need: a way to enumerate a vertex's neighbors. Any object that provides that interface is an adjacency list, even if it computes answers on demand.

Formal algorithms courses (MIT 6.006, Stanford CS161) define BFS and DFS in terms of this neighbor abstraction, which is why they apply uniformly to explicit and implicit graphs alike.

# Implicit graph: word ladder BFS
from collections import deque

def word_neighbors(word, word_set):
    """All words in word_set reachable by 1-letter change."""
    for i in range(len(word)):
        for c in 'abcdefghijklmnopqrstuvwxyz':
            candidate = word[:i] + c + word[i+1:]
            if candidate != word and candidate in word_set:
                yield candidate

def word_ladder(start, end, word_list):
    word_set = set(word_list)
    if end not in word_set:
        return -1
    visited = {start}
    queue = deque([(start, 1)])
    while queue:
        word, dist = queue.popleft()
        for nxt in word_neighbors(word, word_set):
            if nxt == end:
                return dist + 1
            if nxt not in visited:
                visited.add(nxt)
                queue.append((nxt, dist + 1))
    return -1

words = ["hot","dot","dog","lot","log","cog"]
print(word_ladder("hit", "cog", words))  # 5

This is the practical synthesis. Here is the principled decision process used by experienced engineers and researchers:

Use an adjacency matrix when:

1. The graph is dense (E = Ω(V²)) — the extra space is unavoidable anyway.
2. You need O(1) edge existence queries frequently (e.g., detecting multi-edges during construction, or the inner loop of Floyd-Warshall).
3. V is small (V ≤ 1,000 is usually fine; V ≤ 10,000 is feasible with care).
4. You need algebraic operations on the graph (spectral analysis, matrix powers for walk counting).
5. The graph structure changes very frequently (add/remove edges): matrix gives O(1) updates.

Use an adjacency list when:

1. The graph is sparse (E = O(V) or E = O(V log V)) — the savings are enormous.
2. You're running BFS, DFS, Dijkstra, Bellman-Ford, topological sort, SCC — any algorithm whose complexity depends on E.
3. V is large (hundreds of thousands or millions of vertices).
4. You're implementing a general-purpose graph library where you don't know the density in advance.
5. You need to iterate over all neighbors efficiently.

Use CSR (or similar) when:

1. You need maximum cache performance at scale.
2. The graph is static (edges don't change after construction).
3. You're integrating with scientific computing libraries (scipy, PyTorch Geometric, etc.).
4. Memory is tight and you need to minimize overhead.

Use an implicit/on-the-fly representation when:

1. The graph is astronomically large (search spaces, game trees).
2. The neighbor function has a closed-form formula (grids, combinations, permutations).
3. You only need to traverse the graph, not store it.

The universal rule: match the representation to the algorithm's dominant operation. If the algorithm says 'for each neighbor of u', use a list. If it says 'check if (u,v) is an edge', use a matrix or hash set.

# Decision helper pseudocode
def choose_representation(V, E, operations):
    density = E / (V * V)  # 0 = sparse, 1 = dense

    if V > 10_000 or density < 0.1:
        # Must use list: matrix would be too large
        if E / V < 100 and is_static_graph:
            return "CSR (best cache perf, static)"
        else:
            return "Adjacency List (flexible, dynamic)"

    if density > 0.5:
        return "Adjacency Matrix (dense, O(1) lookup)"

    if operations.requires_o1_edge_check:
        if V < 5000:
            return "Adjacency Matrix"
        else:
            return "Adjacency List with hash set per vertex"

    return "Adjacency List (general default)"