Space Complexity — O(V + E)

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

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

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

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]

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

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!

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