Data Structures & AlgorithmsGraph Representation — Adjacency List

Graph Representation — Adjacency List

LevelIntermediate

Duration60 mins

TopicGraph Representation — Adjacency List

2 / 4

Space Complexity — O(V + E)

Understanding the True Cost of Storage

When we say an adjacency list uses O(V + E) space, we're making a profound statement about efficiency. This isn't just an abstract complexity class—it represents a fundamental alignment between the storage we use and the actual information content of the graph.

Unlike the adjacency matrix which reserves space for all possible edges, the adjacency list stores only what exists. This difference isn't merely linear—for sparse graphs, it can be the difference between gigabytes and petabytes, between feasibility and impossibility.

Let's rigorously understand where every byte goes and why this representation achieves optimal space efficiency for sparse graphs.

What You Will Learn

By the end of this page, you will understand exactly how O(V + E) space is distributed in an adjacency list, why this is asymptotically optimal for representing a graph, how constant factors affect real memory usage, and when this space profile makes adjacency lists the clear choice over matrices.

Breaking Down O(V + E): Where Every Unit Goes

The O(V + E) notation combines two distinct components, each serving a specific purpose:

The O(V) Component: Vertex Infrastructure

For each vertex in the graph, we need:

An entry in the main array/map — A reference or pointer to that vertex's neighbor collection
Metadata for the neighbor collection — Length, capacity, or pointer to first element
Optional vertex data — Labels, weights, or other vertex-specific information

This is O(V) because we have exactly one entry per vertex, regardless of how many edges exist.

1
2
3
4
5
6
7
8
9
10
11
12
Main Array (stores references to neighbor lists):
┌───────┬───────┬───────┬───────┬───────┐
│ ptr_0 │ ptr_1 │ ptr_2 │ ptr_3 │ ptr_4 │  ← 5 array slots (O(V))
└───────┴───────┴───────┴───────┴───────┘
 
Each pointer references a dynamic array with its own overhead:
  - Array object header (language-dependent, typically 12-24 bytes)
  - Length field (4-8 bytes)
  - Capacity field (4-8 bytes in some implementations)
  - Pointer to actual data (8 bytes on 64-bit systems)
 
Total vertex infrastructure: O(V) × constant per vertex

The O(E) Component: Edge Storage

For each edge in the graph, we need to store the endpoint(s):

In an undirected graph: Each edge (u, v) appears in both adj[u] and adj[v], creating 2 entries per edge. Total: 2|E| entries.
In a directed graph: Each edge u → v appears only in adj[u], creating 1 entry per edge. Total: |E| entries.

Both cases are O(E), differing only by a constant factor of 2.

1
2
3
4
5
6
7
8
9
10
11
12
13
Undirected Graph with 4 edges:
Edges: (0,1), (0,2), (1,2), (2,3)
 
Adjacency List:
Vertex 0: [1, 2]      ← 2 entries
Vertex 1: [0, 2]      ← 2 entries
Vertex 2: [0, 1, 3]   ← 3 entries
Vertex 3: [2]         ← 1 entry
                      ────────────
Total edge entries:      8 entries = 2 × |E| = 2 × 4
 
For weighted graphs, each entry is (neighbor, weight):
Vertex 0: [(1, 5.0), (2, 3.0)]   ← Still 2 entries, each larger

Summing Up

Total space = O(V) for vertex infrastructure + O(E) for edge entries = O(V + E). For sparse graphs where E << V², this is dramatically smaller than the O(V²) required by adjacency matrices.

Sparse vs Dense: When O(V + E) Wins

The power of O(V + E) becomes apparent when we compare it to the O(V²) of adjacency matrices across different graph densities.

Graph Density Defined:

Sparse graph: |E| = O(V) — edges proportional to vertices (e.g., trees, road networks)
Moderately sparse: |E| = O(V log V) or O(V√V)
Dense graph: |E| = O(V²) — edges proportional to square of vertices
Complete graph: |E| = V(V-1)/2 — every pair connected

Space Comparison: Adjacency List vs Matrix
Vertices (V)	Edges (E)	Graph Type	Adj List O(V+E)	Matrix O(V²)	List Advantage
1,000	999	Tree	~2K entries	1M entries	500× smaller
1,000	5,000	Sparse (5E/V)	~6K entries	1M entries	167× smaller
1,000	50,000	Moderate (50E/V)	~51K entries	1M entries	20× smaller
1,000	499,500	Complete	~500K entries	1M entries	2× smaller
1,000,000	2,000,000	Sparse (2E/V)	~3M entries	1T entries	333,333× smaller
1,000,000	500B	Complete	~500B entries	1T entries	~2× smaller

The Critical Insight:

For sparse graphs (where |E| = O(V)), adjacency lists use O(V) space while matrices use O(V²). As V grows, the ratio becomes astronomical:

V = 1,000: Matrix uses 1,000× more space
V = 1,000,000: Matrix uses 1,000,000× more space
V = 1,000,000,000: Matrix needs ~10¹⁸ cells (physically impossible)

This is why real-world graph applications—social networks, web graphs, road networks—universally use adjacency lists or variations thereof.

The Crossover Point

Adjacency lists and matrices use roughly equal space when |E| ≈ V²/2. For denser graphs, matrices may actually be more space-efficient due to lower per-entry overhead. In practice, switch to matrices when density > 50% AND constant-time edge lookup is critical.

Beyond Big-O: Constant Factors in Real Memory

Big-O notation hides constant factors, but real systems have real memory limits. Let's examine the actual memory usage of adjacency list implementations:

Per-Vertex Overhead:

Each vertex's neighbor collection has associated overhead that varies by language and implementation:

Per-Vertex Memory Overhead by Language
Language	Empty List/Vector Overhead	Notes
Python (list)	~56 bytes	Object header + length + allocated capacity + pointer
Java (ArrayList)	~48 bytes	Object header + size + modCount + array reference
C++ (vector)	~24 bytes	3 pointers: begin, end, capacity (on 64-bit)
Rust (Vec)	~24 bytes	pointer + length + capacity
Go (slice)	~24 bytes	pointer + length + capacity

Per-Edge Memory:

Each neighbor entry costs memory based on the data stored:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
Unweighted graph (store neighbor index only):
  - 32-bit integer index: 4 bytes per neighbor
  - 64-bit integer index: 8 bytes per neighbor
 
Weighted graph (neighbor + weight):
  - (int32 neighbor, float32 weight): 8 bytes
  - (int64 neighbor, float64 weight): 16 bytes
  - Python tuple (neighbor, weight): ~64+ bytes (object overhead!)
 
Edge with full metadata:
  - struct Edge { int dest; double weight; int capacity; int id; }
  - Typically 24-32 bytes per edge
 
# Example: 1 million vertices, 10 million edges (sparse, 10 edges/vertex)
# Using 32-bit indices for unweighted graph:
 
Vertex overhead:  1,000,000 vertices × 24 bytes = 24 MB
Edge storage:    10,000,000 edges × 2 × 4 bytes = 80 MB (×2 for undirected)
                                           ─────────────
Total:                                      ~104 MB
 
# Adjacency matrix for same graph:
1,000,000² × 1 bit = 125 GB (even with bit-packing!)
1,000,000² × 1 byte = 1 TB

Python's Hidden Costs

In Python, storing edges as tuple objects (neighbor, weight) can use 64+ bytes per edge due to object overhead. For memory-critical applications, use NumPy arrays or struct-based approaches. A graph with 100M edges could use 6.4 GB with tuples vs 800 MB with NumPy int32 arrays.

Memory Layout and Cache Considerations

Space complexity isn't just about total memory—how that memory is organized affects performance through CPU cache behavior.

The Fragmentation Problem:

A naive adjacency list (array of separate arrays) scatters neighbor data across memory. When iterating through different vertices' neighbors, we suffer cache misses:

Main array: [ptr0, ptr1, ptr2, ptr3, ...]
               ↓     ↓     ↓
Memory:    [neighbors0]....[neighbors1]....[neighbors2]
           scattered across heap

Each vertex's neighbor traversal may start with a cache miss to load that vertex's neighbor array.

Compressed Sparse Row (CSR) Format:

For better cache performance, store all neighbors contiguously in a single array, with an index array marking where each vertex's neighbors begin:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
class CSRGraph:
    """
    Compressed Sparse Row format for cache-efficient graph storage.
    
    All neighbors stored contiguously in one array.
    Index array marks where each vertex's neighbors start.
    
    Memory: Single allocation for all edges = better cache locality
    """
    
    def __init__(self, num_vertices: int, edges: list[tuple[int, int]]):
        # First pass: count edges per vertex
        degrees = [0] * num_vertices
        for u, v in edges:
            degrees[u] += 1
            degrees[v] += 1  # for undirected
        
        # Build index array: where does each vertex's neighbors start?
        # index[v] = starting position of vertex v's neighbors
        # index[V] = total number of neighbor entries (sentinel)
        self.index = [0] * (num_vertices + 1)
        for v in range(num_vertices):
            self.index[v + 1] = self.index[v] + degrees[v]
        
        # Build neighbors array with all neighbors contiguous
        self.neighbors = [0] * self.index[num_vertices]
        
        # Reset degrees to use as insertion pointers
        insert_pos = self.index[:-1].copy()
        for u, v in edges:
            self.neighbors[insert_pos[u]] = v
            insert_pos[u] += 1
            self.neighbors[insert_pos[v]] = u  # for undirected
            insert_pos[v] += 1
        
        self.V = num_vertices
    
    def get_neighbors(self, v: int):
        """Return a view/slice of the neighbors array for vertex v."""
        start = self.index[v]
        end = self.index[v + 1]
        return self.neighbors[start:end]
    
    def degree(self, v: int) -> int:
        """Degree can be computed from index array."""
        return self.index[v + 1] - self.index[v]
 
# Example
edges = [(0,1), (0,2), (1,2), (2,3), (3,4)]
g = CSRGraph(5, edges)
 
print(f"Index array: {g.index}")      
# [0, 2, 4, 7, 9, 10]
# Vertex 0 neighbors at positions 0-1, vertex 1 at 2-3, etc.
 
print(f"Neighbors array: {g.neighbors}")  
# [1, 2, 0, 2, 0, 1, 3, 2, 4, 3]
# All neighbors stored contiguously!
 
print(f"Neighbors of vertex 2: {g.get_neighbors(2)}")  
# [0, 1, 3]

Cache Performance Comparison
Format	Memory Allocations	Cache Behavior	Best For
Array of Arrays	V + 1 allocations	Cache misses per vertex	Dynamic graphs, frequent modifications
CSR (Compressed)	2 allocations	Sequential, cache-friendly	Static graphs, repeated traversals
Array of Hash Sets	V + 1 allocations	Random access within sets	Frequent edge existence queries

Formal Comparison: Adjacency List vs Matrix Space

Let's formalize when each representation is more space-efficient, accounting for the storage size of different data types.

Adjacency List Space:

Vertex pointers/headers: V × P where P = pointer/header size
Edge entries: 2E × I for undirected (I = integer size for neighbor index)
Total: V × P + 2E × I

Adjacency Matrix Space:

Matrix cells: V² × C where C = cell size (1 bit, 1 byte, or more for weighted)

Crossover Analysis:

List is better when: V × P + 2E × I < V² × C

Solving for E: E < (V² × C - V × P) / (2 × I)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
def crossover_density(V: int, 
                        pointer_size: int = 8,    # bytes per vertex header
                        index_size: int = 4,      # bytes per neighbor index
                        cell_size: float = 0.125  # bytes per matrix cell (1 bit = 0.125)
                       ) -> float:
    """
    Calculate the edge density at which list and matrix use equal space.
    
    Returns the density as a fraction of maximum possible edges.
    """
    max_edges = V * (V - 1) // 2  # undirected complete graph
    
    # Space: V*P + 2*E*I = V² * C
    # Solving for E: E = (V² * C - V * P) / (2 * I)
    crossover_edges = (V**2 * cell_size - V * pointer_size) / (2 * index_size)
    
    if crossover_edges <= 0:
        return 0.0  # List always better for this configuration
    
    return crossover_edges / max_edges
 
# Examples with different configurations
print("Crossover density (list vs matrix equal space):")
print(f"  V=100, bit-matrix:   {crossover_density(100):.2%}")   # ~1.5%
print(f"  V=100, byte-matrix:  {crossover_density(100, cell_size=1):.2%}")  # ~12%
print(f"  V=1000, bit-matrix:  {crossover_density(1000):.2%}")  # ~0.15%
print(f"  V=1000, byte-matrix: {crossover_density(1000, cell_size=1):.2%}")  # ~12.4%
 
# Key insight: For bit-packed matrices, crossover is ~1/8 = 12.5% density
# For byte matrices, crossover is ~50% density (accounting for overhead)
# In practice, matrices win only for dense graphs or when weighted

Practical Guidelines:

Graph Density	Edges	Recommended Representation
< 1%	E < V²/100	Adjacency List (no contest)
1-10%	V² / 100 ≤ E < V² / 10	Adjacency List
10-50%	V² / 10 ≤ E < V² / 2	Either; depends on access patterns
> 50%	E > V² / 2	Consider Matrix

Most real-world graphs fall in the < 1% category, which is why adjacency lists dominate in practice.

Weighted Graphs Change the Calculus

For weighted graphs, matrix cells need more space (4-8 bytes for weights), shifting the crossover toward lists. A weighted adjacency list stores (neighbor, weight) pairs—essentially the same information matrix cells would store—but only for edges that exist.

Space Considerations for Weighted and Special Graphs

Real-world graphs often carry additional data beyond simple connectivity. Let's analyze space requirements for common variants:

Weighted Graphs:

Each edge entry grows to include weight data:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
# Unweighted: neighbor index only
# Space per edge entry: sizeof(int) = 4 bytes
 
# Weighted with float weight:
# Space per edge entry: sizeof(int) + sizeof(float) = 8 bytes
 
# Weighted with metadata (distance, time, cost):
# struct Edge { int dest; float distance; float time; float cost; }
# Space per edge entry: 4 + 4 + 4 + 4 = 16 bytes
 
# Total space for weighted undirected graph:
# V × pointer_overhead + 2E × entry_size
 
def weighted_graph_memory(V: int, E: int, 
                          vertex_overhead: int = 24,
                          entry_bytes: int = 8) -> int:
    """Calculate memory in bytes for weighted adjacency list."""
    vertex_memory = V * vertex_overhead
    edge_memory = 2 * E * entry_bytes  # ×2 for undirected
    return vertex_memory + edge_memory
 
# Example: Road network with 1M intersections, 2.5M road segments
V, E = 1_000_000, 2_500_000
mem = weighted_graph_memory(V, E, entry_bytes=16)  # with distance+time
print(f"Memory: {mem / 1e6:.1f} MB")  # ~104 MB
 
# Same as matrix?
matrix_mem = V * V * 16  # 16 bytes per cell for weights
print(f"Matrix would need: {matrix_mem / 1e12:.1f} TB")  # 16 TB!

Multigraphs (Multiple Edges Between Same Vertices):

Multigraphs allow multiple edges between the same pair of vertices (e.g., different flight routes between two cities). Adjacency lists naturally accommodate this—just add multiple entries:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# Multigraph: Multiple flights between same cities
# NYC → LA: Flight 1 (morning, $200), Flight 2 (evening, $300)
 
# Adjacency list naturally handles this:
adj = {
    "NYC": [
        ("LA", {"id": "F1", "time": "08:00", "price": 200}),
        ("LA", {"id": "F2", "time": "18:00", "price": 300}),
        ("CHI", {"id": "F3", "time": "10:00", "price": 100}),
    ],
    "LA": [
        ("NYC", {"id": "F4", "time": "06:00", "price": 220}),
    ],
    # ...
}
 
# Space: O(V + E) where E counts ALL edges, including parallel ones
# No special handling needed—parallel edges just add more entries

Self-Loops

Self-loops (edges from a vertex to itself) also store naturally in adjacency lists—vertex v's neighbor list simply includes v. The O(V + E) analysis remains unchanged; self-loops just count as edges. In a matrix, self-loops occupy diagonal cells.

Summary: The Space Efficiency of Adjacency Lists

We've thoroughly analyzed the O(V + E) space complexity of adjacency lists and understood when and why it matters. Let's consolidate the key insights:

Key Takeaways

•O(V + E) means proportional storage — Space scales with actual graph content, not theoretical maximum. This is asymptotically optimal for representing a graph.
•The V component is vertex infrastructure — Array slots, pointers, and collection metadata; constant per vertex regardless of connectivity.
•The E component is edge storage — 2E entries for undirected graphs (each edge stored twice), E entries for directed graphs.
•Sparse graphs benefit enormously — When E = O(V), adjacency lists use O(V) space vs O(V²) for matrices—a difference of V× for large graphs.
•Constant factors matter in practice — Object overhead in high-level languages can significantly inflate memory usage. Use primitive arrays or structs for large graphs.
•Cache-friendly formats exist — CSR (Compressed Sparse Row) stores all neighbors contiguously for better cache performance during traversals.
•Weighted graphs scale similarly — Entry size grows to accommodate weights, but the fundamental O(V + E) structure remains.

What's Next:

Having understood space complexity, the next page analyzes time complexity for edge operations—specifically, why edge lookup in an adjacency list takes O(degree) time and what this means for algorithm design.

Page Complete

You now understand that O(V + E) space makes adjacency lists the go-to representation for sparse graphs. This proportional storage—using space only for actual edges—enables representation of graphs that would be impossible with O(V²) matrices.

2 / 4

Loading learning content...

Data Structures & AlgorithmsGraph Representation — Adjacency List

Graph Representation — Adjacency List

LevelIntermediate

Duration60 mins

TopicGraph Representation — Adjacency List

2 / 4

Space Complexity — O(V + E)

Understanding the True Cost of Storage

Let's rigorously understand where every byte goes and why this representation achieves optimal space efficiency for sparse graphs.

What You Will Learn

Breaking Down O(V + E): Where Every Unit Goes

The O(V + E) notation combines two distinct components, each serving a specific purpose:

The O(V) Component: Vertex Infrastructure

For each vertex in the graph, we need:

An entry in the main array/map — A reference or pointer to that vertex's neighbor collection
Metadata for the neighbor collection — Length, capacity, or pointer to first element
Optional vertex data — Labels, weights, or other vertex-specific information

This is O(V) because we have exactly one entry per vertex, regardless of how many edges exist.

1
2
3
4
5
6
7
8
9
10
11
12
Main Array (stores references to neighbor lists):
┌───────┬───────┬───────┬───────┬───────┐
│ ptr_0 │ ptr_1 │ ptr_2 │ ptr_3 │ ptr_4 │  ← 5 array slots (O(V))
└───────┴───────┴───────┴───────┴───────┘
 
Each pointer references a dynamic array with its own overhead:
  - Array object header (language-dependent, typically 12-24 bytes)
  - Length field (4-8 bytes)
  - Capacity field (4-8 bytes in some implementations)
  - Pointer to actual data (8 bytes on 64-bit systems)
 
Total vertex infrastructure: O(V) × constant per vertex

The O(E) Component: Edge Storage

For each edge in the graph, we need to store the endpoint(s):

In an undirected graph: Each edge (u, v) appears in both adj[u] and adj[v], creating 2 entries per edge. Total: 2|E| entries.
In a directed graph: Each edge u → v appears only in adj[u], creating 1 entry per edge. Total: |E| entries.

Both cases are O(E), differing only by a constant factor of 2.

1
2
3
4
5
6
7
8
9
10
11
12
13
Undirected Graph with 4 edges:
Edges: (0,1), (0,2), (1,2), (2,3)
 
Adjacency List:
Vertex 0: [1, 2]      ← 2 entries
Vertex 1: [0, 2]      ← 2 entries
Vertex 2: [0, 1, 3]   ← 3 entries
Vertex 3: [2]         ← 1 entry
                      ────────────
Total edge entries:      8 entries = 2 × |E| = 2 × 4
 
For weighted graphs, each entry is (neighbor, weight):
Vertex 0: [(1, 5.0), (2, 3.0)]   ← Still 2 entries, each larger

Summing Up

Total space = O(V) for vertex infrastructure + O(E) for edge entries = O(V + E). For sparse graphs where E << V², this is dramatically smaller than the O(V²) required by adjacency matrices.

Sparse vs Dense: When O(V + E) Wins

The power of O(V + E) becomes apparent when we compare it to the O(V²) of adjacency matrices across different graph densities.

Graph Density Defined:

Sparse graph: |E| = O(V) — edges proportional to vertices (e.g., trees, road networks)
Moderately sparse: |E| = O(V log V) or O(V√V)
Dense graph: |E| = O(V²) — edges proportional to square of vertices
Complete graph: |E| = V(V-1)/2 — every pair connected

Space Comparison: Adjacency List vs Matrix
Vertices (V)	Edges (E)	Graph Type	Adj List O(V+E)	Matrix O(V²)	List Advantage
1,000	999	Tree	~2K entries	1M entries	500× smaller
1,000	5,000	Sparse (5E/V)	~6K entries	1M entries	167× smaller
1,000	50,000	Moderate (50E/V)	~51K entries	1M entries	20× smaller
1,000	499,500	Complete	~500K entries	1M entries	2× smaller
1,000,000	2,000,000	Sparse (2E/V)	~3M entries	1T entries	333,333× smaller
1,000,000	500B	Complete	~500B entries	1T entries	~2× smaller

The Critical Insight:

For sparse graphs (where |E| = O(V)), adjacency lists use O(V) space while matrices use O(V²). As V grows, the ratio becomes astronomical:

V = 1,000: Matrix uses 1,000× more space
V = 1,000,000: Matrix uses 1,000,000× more space
V = 1,000,000,000: Matrix needs ~10¹⁸ cells (physically impossible)

This is why real-world graph applications—social networks, web graphs, road networks—universally use adjacency lists or variations thereof.

The Crossover Point

Beyond Big-O: Constant Factors in Real Memory

Big-O notation hides constant factors, but real systems have real memory limits. Let's examine the actual memory usage of adjacency list implementations:

Per-Vertex Overhead:

Each vertex's neighbor collection has associated overhead that varies by language and implementation:

Per-Vertex Memory Overhead by Language
Language	Empty List/Vector Overhead	Notes
Python (list)	~56 bytes	Object header + length + allocated capacity + pointer
Java (ArrayList)	~48 bytes	Object header + size + modCount + array reference
C++ (vector)	~24 bytes	3 pointers: begin, end, capacity (on 64-bit)
Rust (Vec)	~24 bytes	pointer + length + capacity
Go (slice)	~24 bytes	pointer + length + capacity

Per-Edge Memory:

Each neighbor entry costs memory based on the data stored:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
Unweighted graph (store neighbor index only):
  - 32-bit integer index: 4 bytes per neighbor
  - 64-bit integer index: 8 bytes per neighbor
 
Weighted graph (neighbor + weight):
  - (int32 neighbor, float32 weight): 8 bytes
  - (int64 neighbor, float64 weight): 16 bytes
  - Python tuple (neighbor, weight): ~64+ bytes (object overhead!)
 
Edge with full metadata:
  - struct Edge { int dest; double weight; int capacity; int id; }
  - Typically 24-32 bytes per edge
 
# Example: 1 million vertices, 10 million edges (sparse, 10 edges/vertex)
# Using 32-bit indices for unweighted graph:
 
Vertex overhead:  1,000,000 vertices × 24 bytes = 24 MB
Edge storage:    10,000,000 edges × 2 × 4 bytes = 80 MB (×2 for undirected)
                                           ─────────────
Total:                                      ~104 MB
 
# Adjacency matrix for same graph:
1,000,000² × 1 bit = 125 GB (even with bit-packing!)
1,000,000² × 1 byte = 1 TB

Python's Hidden Costs

Memory Layout and Cache Considerations

Space complexity isn't just about total memory—how that memory is organized affects performance through CPU cache behavior.

The Fragmentation Problem:

A naive adjacency list (array of separate arrays) scatters neighbor data across memory. When iterating through different vertices' neighbors, we suffer cache misses:

Main array: [ptr0, ptr1, ptr2, ptr3, ...]
               ↓     ↓     ↓
Memory:    [neighbors0]....[neighbors1]....[neighbors2]
           scattered across heap

Each vertex's neighbor traversal may start with a cache miss to load that vertex's neighbor array.

Compressed Sparse Row (CSR) Format:

For better cache performance, store all neighbors contiguously in a single array, with an index array marking where each vertex's neighbors begin:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
class CSRGraph:
    """
    Compressed Sparse Row format for cache-efficient graph storage.
    
    All neighbors stored contiguously in one array.
    Index array marks where each vertex's neighbors start.
    
    Memory: Single allocation for all edges = better cache locality
    """
    
    def __init__(self, num_vertices: int, edges: list[tuple[int, int]]):
        # First pass: count edges per vertex
        degrees = [0] * num_vertices
        for u, v in edges:
            degrees[u] += 1
            degrees[v] += 1  # for undirected
        
        # Build index array: where does each vertex's neighbors start?
        # index[v] = starting position of vertex v's neighbors
        # index[V] = total number of neighbor entries (sentinel)
        self.index = [0] * (num_vertices + 1)
        for v in range(num_vertices):
            self.index[v + 1] = self.index[v] + degrees[v]
        
        # Build neighbors array with all neighbors contiguous
        self.neighbors = [0] * self.index[num_vertices]
        
        # Reset degrees to use as insertion pointers
        insert_pos = self.index[:-1].copy()
        for u, v in edges:
            self.neighbors[insert_pos[u]] = v
            insert_pos[u] += 1
            self.neighbors[insert_pos[v]] = u  # for undirected
            insert_pos[v] += 1
        
        self.V = num_vertices
    
    def get_neighbors(self, v: int):
        """Return a view/slice of the neighbors array for vertex v."""
        start = self.index[v]
        end = self.index[v + 1]
        return self.neighbors[start:end]
    
    def degree(self, v: int) -> int:
        """Degree can be computed from index array."""
        return self.index[v + 1] - self.index[v]
 
# Example
edges = [(0,1), (0,2), (1,2), (2,3), (3,4)]
g = CSRGraph(5, edges)
 
print(f"Index array: {g.index}")      
# [0, 2, 4, 7, 9, 10]
# Vertex 0 neighbors at positions 0-1, vertex 1 at 2-3, etc.
 
print(f"Neighbors array: {g.neighbors}")  
# [1, 2, 0, 2, 0, 1, 3, 2, 4, 3]
# All neighbors stored contiguously!
 
print(f"Neighbors of vertex 2: {g.get_neighbors(2)}")  
# [0, 1, 3]

Cache Performance Comparison
Format	Memory Allocations	Cache Behavior	Best For
Array of Arrays	V + 1 allocations	Cache misses per vertex	Dynamic graphs, frequent modifications
CSR (Compressed)	2 allocations	Sequential, cache-friendly	Static graphs, repeated traversals
Array of Hash Sets	V + 1 allocations	Random access within sets	Frequent edge existence queries

Formal Comparison: Adjacency List vs Matrix Space

Let's formalize when each representation is more space-efficient, accounting for the storage size of different data types.

Adjacency List Space:

Vertex pointers/headers: V × P where P = pointer/header size
Edge entries: 2E × I for undirected (I = integer size for neighbor index)
Total: V × P + 2E × I

Adjacency Matrix Space:

Matrix cells: V² × C where C = cell size (1 bit, 1 byte, or more for weighted)

Crossover Analysis:

List is better when: V × P + 2E × I < V² × C

Solving for E: E < (V² × C - V × P) / (2 × I)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
def crossover_density(V: int, 
                        pointer_size: int = 8,    # bytes per vertex header
                        index_size: int = 4,      # bytes per neighbor index
                        cell_size: float = 0.125  # bytes per matrix cell (1 bit = 0.125)
                       ) -> float:
    """
    Calculate the edge density at which list and matrix use equal space.
    
    Returns the density as a fraction of maximum possible edges.
    """
    max_edges = V * (V - 1) // 2  # undirected complete graph
    
    # Space: V*P + 2*E*I = V² * C
    # Solving for E: E = (V² * C - V * P) / (2 * I)
    crossover_edges = (V**2 * cell_size - V * pointer_size) / (2 * index_size)
    
    if crossover_edges <= 0:
        return 0.0  # List always better for this configuration
    
    return crossover_edges / max_edges
 
# Examples with different configurations
print("Crossover density (list vs matrix equal space):")
print(f"  V=100, bit-matrix:   {crossover_density(100):.2%}")   # ~1.5%
print(f"  V=100, byte-matrix:  {crossover_density(100, cell_size=1):.2%}")  # ~12%
print(f"  V=1000, bit-matrix:  {crossover_density(1000):.2%}")  # ~0.15%
print(f"  V=1000, byte-matrix: {crossover_density(1000, cell_size=1):.2%}")  # ~12.4%
 
# Key insight: For bit-packed matrices, crossover is ~1/8 = 12.5% density
# For byte matrices, crossover is ~50% density (accounting for overhead)
# In practice, matrices win only for dense graphs or when weighted

Practical Guidelines:

Graph Density	Edges	Recommended Representation
< 1%	E < V²/100	Adjacency List (no contest)
1-10%	V² / 100 ≤ E < V² / 10	Adjacency List
10-50%	V² / 10 ≤ E < V² / 2	Either; depends on access patterns
> 50%	E > V² / 2	Consider Matrix

Most real-world graphs fall in the < 1% category, which is why adjacency lists dominate in practice.

Weighted Graphs Change the Calculus

Space Considerations for Weighted and Special Graphs

Real-world graphs often carry additional data beyond simple connectivity. Let's analyze space requirements for common variants:

Weighted Graphs:

Each edge entry grows to include weight data:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
# Unweighted: neighbor index only
# Space per edge entry: sizeof(int) = 4 bytes
 
# Weighted with float weight:
# Space per edge entry: sizeof(int) + sizeof(float) = 8 bytes
 
# Weighted with metadata (distance, time, cost):
# struct Edge { int dest; float distance; float time; float cost; }
# Space per edge entry: 4 + 4 + 4 + 4 = 16 bytes
 
# Total space for weighted undirected graph:
# V × pointer_overhead + 2E × entry_size
 
def weighted_graph_memory(V: int, E: int, 
                          vertex_overhead: int = 24,
                          entry_bytes: int = 8) -> int:
    """Calculate memory in bytes for weighted adjacency list."""
    vertex_memory = V * vertex_overhead
    edge_memory = 2 * E * entry_bytes  # ×2 for undirected
    return vertex_memory + edge_memory
 
# Example: Road network with 1M intersections, 2.5M road segments
V, E = 1_000_000, 2_500_000
mem = weighted_graph_memory(V, E, entry_bytes=16)  # with distance+time
print(f"Memory: {mem / 1e6:.1f} MB")  # ~104 MB
 
# Same as matrix?
matrix_mem = V * V * 16  # 16 bytes per cell for weights
print(f"Matrix would need: {matrix_mem / 1e12:.1f} TB")  # 16 TB!

Multigraphs (Multiple Edges Between Same Vertices):

Multigraphs allow multiple edges between the same pair of vertices (e.g., different flight routes between two cities). Adjacency lists naturally accommodate this—just add multiple entries:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# Multigraph: Multiple flights between same cities
# NYC → LA: Flight 1 (morning, $200), Flight 2 (evening, $300)
 
# Adjacency list naturally handles this:
adj = {
    "NYC": [
        ("LA", {"id": "F1", "time": "08:00", "price": 200}),
        ("LA", {"id": "F2", "time": "18:00", "price": 300}),
        ("CHI", {"id": "F3", "time": "10:00", "price": 100}),
    ],
    "LA": [
        ("NYC", {"id": "F4", "time": "06:00", "price": 220}),
    ],
    # ...
}
 
# Space: O(V + E) where E counts ALL edges, including parallel ones
# No special handling needed—parallel edges just add more entries

Self-Loops

Summary: The Space Efficiency of Adjacency Lists

We've thoroughly analyzed the O(V + E) space complexity of adjacency lists and understood when and why it matters. Let's consolidate the key insights:

Key Takeaways

•O(V + E) means proportional storage — Space scales with actual graph content, not theoretical maximum. This is asymptotically optimal for representing a graph.
•The V component is vertex infrastructure — Array slots, pointers, and collection metadata; constant per vertex regardless of connectivity.
•The E component is edge storage — 2E entries for undirected graphs (each edge stored twice), E entries for directed graphs.
•Sparse graphs benefit enormously — When E = O(V), adjacency lists use O(V) space vs O(V²) for matrices—a difference of V× for large graphs.
•Constant factors matter in practice — Object overhead in high-level languages can significantly inflate memory usage. Use primitive arrays or structs for large graphs.
•Cache-friendly formats exist — CSR (Compressed Sparse Row) stores all neighbors contiguously for better cache performance during traversals.
•Weighted graphs scale similarly — Entry size grows to accommodate weights, but the fundamental O(V + E) structure remains.

What's Next:

Page Complete

2 / 4