Graph Representation Tradeoffs - Learning Module

Loading content...

0/279

Choosing the Right Representation

The Decision Framework

You've now mastered the theoretical foundations: space complexity, time complexity for every operation, and the critical role of graph density. But theory alone doesn't ship code. What you need is a systematic decision framework—a reliable process that takes you from problem description to optimal representation choice in seconds.

This page synthesizes everything into actionable decision procedures. You'll learn to recognize patterns instantly, apply quick heuristics for common cases, and conduct thorough analysis when the choice isn't obvious. By the end, selecting the right graph representation will become second nature.

What You Will Learn

By the end of this page, you will have a step-by-step decision process for representation choice, understand quick heuristics that work 95% of the time, recognize the edge cases that require careful analysis, and be able to justify your choices with concrete reasoning.

The Five-Step Decision Process

For any graph problem, follow this systematic process:

Step 1: Characterize the Graph

What is |V| (vertex count)?
What is |E| (edge count)?
Compute density = |E| / max_edges
Is the graph static (never changes) or dynamic (edges/vertices added/removed)?
Is it directed or undirected?
Is it weighted or unweighted?

Step 2: Identify Dominant Operations

Ask: which operations does my algorithm perform most frequently?

Heavy edge querying → favor matrix
Heavy neighbor iteration → favor list
Heavy modification → consider implementation variants
Mixed operations → analyze relative frequencies

Step 3: Apply Quick Heuristics

•If density < 10% → Use adjacency list (almost always correct)
•If density > 25% AND |V| < 5,000 → Consider adjacency matrix
•If graph is dynamic → Use adjacency list (matrices can't grow efficiently)
•If algorithm is traversal-based (BFS, DFS, Dijkstra) → Use adjacency list
•If algorithm needs O(1) edge queries constantly → Consider matrix or hash-set neighbors
•If |V| > 10,000 → Use adjacency list unless you have a very specific reason not to

Step 4: Consider Memory Constraints

Calculate exact memory usage for each option
Matrix: |V|² × bytes_per_cell
List: |V| × overhead_per_vertex + |E| × bytes_per_edge
Consider cache effects for your access patterns

Step 5: Prototype and Measure (if critical)

For performance-critical systems:

Implement both representations
Benchmark with realistic data
Profile actual cache behavior
Choose based on measured performance, not just theory

The 95% Rule

In practice, adjacency lists are correct for ~95% of real-world applications. If you're unsure, start with a list—you'll rarely be wrong. Only deviate when you have specific evidence that a matrix is better for your particular use case.

The Visual Decision Tree

For quick decisions, follow this decision tree. Start at the top and follow branches based on your answers:

                    ┌─────────────────────┐
                    │ Is |V| > 10,000?    │
                    └──────────┬──────────┘
                               │
              ┌────────────────┴────────────────┐
              │ YES                             │ NO
              ▼                                 ▼
   ┌───────────────────┐           ┌───────────────────────┐
   │ Use Adjacency     │           │ Is the graph dynamic  │
   │ List (always)     │           │ (vertices/edges       │
   │                   │           │  added/removed)?      │
   └───────────────────┘           └───────────┬───────────┘
                                               │
                          ┌────────────────────┴────────────────────┐
                          │ YES                                     │ NO
                          ▼                                         ▼
               ┌───────────────────┐               ┌────────────────────────┐
               │ Use Adjacency     │               │ Is density > 25%?      │
               │ List              │               │                        │
               └───────────────────┘               └───────────┬────────────┘
                                                               │
                                      ┌────────────────────────┴─────────────────────────┐
                                      │ YES                                              │ NO
                                      ▼                                                  ▼
                     ┌─────────────────────────────────┐            ┌────────────────────────┐
                     │ Does algorithm need O(1) edge   │            │ Use Adjacency List     │
                     │ queries more than O(degree)     │            │                        │
                     │ neighbor iteration?             │            └────────────────────────┘
                     └───────────────┬─────────────────┘
                                     │
                    ┌────────────────┴────────────────┐
                    │ YES                             │ NO
                    ▼                                 ▼
         ┌───────────────────┐           ┌───────────────────┐
         │ Use Adjacency     │           │ Use Adjacency     │
         │ Matrix            │           │ List              │
         └───────────────────┘           └───────────────────┘

Notice the Pattern

Every path through the decision tree leads to 'Use Adjacency List' except one very specific case: small graphs (|V| < 10,000), static structure, high density (>25%), and algorithms dominated by edge queries. This reflects the real-world truth that adjacency lists are almost always right.

Common Scenarios: Quick Reference Guide

Here's a quick reference for common graph problems and their optimal representations:

Representation Choice by Problem Type
Problem/Algorithm	Typical Density	Dominant Operation	Recommendation
Social Network Analysis	<0.01%	Neighbor iteration	Adjacency List
Web Crawling/PageRank	<0.001%	Neighbor iteration	Adjacency List
Road Network Navigation	<0.01%	Neighbor iteration	Adjacency List
BFS/DFS Traversal	Any	Neighbor iteration	Adjacency List
Dijkstra's Algorithm	Usually sparse	Neighbor iteration	Adjacency List
Bellman-Ford	Usually sparse	Edge iteration	Adjacency List
Topological Sort	Usually sparse	Neighbor iteration	Adjacency List
Connected Components	Usually sparse	Neighbor iteration	Adjacency List
Minimum Spanning Tree	Usually sparse	Edge iteration	Adjacency List
Floyd-Warshall APSP	Any	Edge queries O(V³)	Adjacency Matrix
Complete Graph K_n	100%	All operations	Adjacency Matrix
Small Dense Subproblem	25%, \|V\|<1000	Mixed	Adjacency Matrix
Similarity/Correlation	100%	Edge queries	Adjacency Matrix (it IS one)
Dynamic Connectivity	Varies	Edge modification	Adjacency List + Union-Find

Always Use Adjacency List

•Social media graphs (billions of users)
•Web graphs (billions of pages)
•Road networks (millions of intersections)
•Knowledge graphs (millions of entities)
•Dependency graphs (packages, modules)
•Citation networks (papers, patents)
•Any dynamic graph that grows
•Any graph loaded from external data

Consider Adjacency Matrix

•Floyd-Warshall all-pairs shortest paths
•Tournament scheduling (complete graph)
•Small clique detection subproblems
•Similarity/correlation matrices
•Graph powers (A², A³, etc.)
•Small static graphs (|V| < 500)
•Matrix-based graph algorithms
•Theoretical analysis / proofs

Case Study: Building a Friend Recommendation System

Let's apply our decision framework to a real engineering scenario.

The Problem:

You're building a friend recommendation system for a social network. Given a user, recommend "friends of friends" who aren't already friends. The network has:

10 million users
Average 200 friends per user
Users added continuously
Friendships created/removed frequently

Step 1: Characterize the Graph

|V| = 10,000,000
|E| ≈ (10M × 200) / 2 = 1,000,000,000 edges
Density = 1B / (10M × 10M / 2) ≈ 0.00002% — extremely sparse
Dynamic: users and friendships constantly changing
Undirected (friendship is mutual)
Unweighted

Step 2: Identify Dominant Operations

For friend-of-friend recommendations:

for each friend F of user U:
    for each friend FF of F:
        if FF not in U.friends and FF != U:
            recommend.add(FF)

Dominant operation: neighbor iteration (iterating friends of friends)
Secondary operation: membership check (is FF already a friend?)
Edge queries: rare (only for duplicate checking, can use a Set)

Step 3: Apply Heuristics

Density < 10%? Yes (0.00002%) → List
Graph dynamic? Yes → List
|V| > 10,000? Yes (10M) → List

Every heuristic points to adjacency list.

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
interface SocialGraph {
    // Adjacency list representation
    adjacency: Map<string, Set<string>>;  // userId -> Set of friend userIds
}
 
function recommendFriends(
    graph: SocialGraph, 
    userId: string, 
    maxRecommendations: number = 10
): string[] {
    const userFriends = graph.adjacency.get(userId);
    if (!userFriends) return [];
    
    // Count how many mutual friends each potential recommendation has
    const mutualCount = new Map<string, number>();
    
    // O(degree(user) × average_degree) - efficient with list representation
    for (const friend of userFriends) {  // Iterate neighbors: O(degree)
        const friendsOfFriend = graph.adjacency.get(friend);
        if (!friendsOfFriend) continue;
        
        for (const fof of friendsOfFriend) {  // Iterate neighbors again
            // Skip if already friend or self
            if (fof === userId || userFriends.has(fof)) continue;  // O(1) Set lookup
            
            mutualCount.set(fof, (mutualCount.get(fof) ?? 0) + 1);
        }
    }
    
    // Sort by mutual friend count, return top recommendations
    return [...mutualCount.entries()]
        .sort((a, b) => b[1] - a[1])
        .slice(0, maxRecommendations)
        .map(([userId, _count]) => userId);
}
 
// Memory analysis:
// Matrix would need: 10M × 10M × 1 byte = 100 TB (IMPOSSIBLE)
// List uses: ~10M × overhead + 2B × ~8 bytes ≈ 16 GB (manageable)

Decision: Adjacency List

The choice is unambiguous. An adjacency matrix would require 100 terabytes—physically impossible for this scale. The adjacency list fits in memory (with careful engineering) and perfectly matches our neighbor iteration workload. Using hash sets for neighbor storage gives us O(1) friend-check as a bonus.

Case Study: All-Pairs Shortest Paths in a Small Network

Now let's examine a scenario where the matrix might win.

The Problem:

You're computing latency between all pairs of servers in a data center network:

500 servers
Nearly full mesh connectivity (for redundancy)
About 100,000 connections
Network is static (reconfigure rarely)
Need all-pairs shortest paths for routing decisions

Step 1: Characterize the Graph

|V| = 500
|E| = 100,000
Max edges = 500 × 499 / 2 = 124,750
Density = 100,000 / 124,750 ≈ 80% — very dense
Static: rarely changes
Undirected (latency is symmetric)
Weighted (latency in milliseconds)

Step 2: Identify Dominant Operations

For all-pairs shortest paths:

Floyd-Warshall: O(|V|³) edge queries
Output: |V|² distance values

Dominant operation: constant edge queries in the innermost loop.

Step 3: Apply Heuristics

Density > 25%? Yes (80%) → Consider matrix
|V| < 10,000? Yes (500) → Matrix is feasible
Graph static? Yes → Matrix OK
Algorithm needs O(1) edge queries? Yes (Floyd-Warshall) → Matrix favored

This is one of the rare cases where matrix is optimal!

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
function floydWarshall(latencyMatrix: number[][]): number[][] {
    const n = latencyMatrix.length;
    
    // Initialize distance matrix (copy of input)
    // Already an adjacency matrix - no conversion needed!
    const dist = latencyMatrix.map(row => [...row]);
    
    // Set self-distances to 0, unreachable to Infinity
    for (let i = 0; i < n; i++) {
        dist[i][i] = 0;
        for (let j = 0; j < n; j++) {
            if (i !== j && dist[i][j] === 0) {
                dist[i][j] = Infinity;  // No direct edge
            }
        }
    }
    
    // Floyd-Warshall: O(V³)
    // Every operation in the inner loop is O(1) thanks to matrix representation
    for (let k = 0; k < n; k++) {
        for (let i = 0; i < n; i++) {
            for (let j = 0; j < n; j++) {
                // This edge query is O(1) with matrix
                // Would be O(degree) with naive adjacency list
                if (dist[i][k] + dist[k][j] < dist[i][j]) {
                    dist[i][j] = dist[i][k] + dist[k][j];
                }
            }
        }
    }
    
    return dist;
}
 
// Memory analysis:
// Matrix: 500 × 500 × 8 bytes (float64) = 2 MB (trivial)
// Output is also 500 × 500 = inherently matrix-shaped
 
// Performance analysis:
// With matrix: 500³ × O(1) = 125 million simple operations
// With list: Would need edge lookup in inner loop - much slower

Decision: Adjacency Matrix

This is a textbook matrix use case: small graph, high density, static structure, and an algorithm (Floyd-Warshall) specifically designed for matrix representation. The matrix uses only 2 MB—trivial—and the algorithm's innermost loop benefits from O(1) edge access. The output is also a matrix, making the representation natural end-to-end.

Edge Cases and Special Considerations

Not every decision is clear-cut. Here are situations that require careful thought:

Edge Case 1: Moderate Density, Mixed Operations

When density is 10-25% and your algorithm both queries edges and iterates neighbors frequently, the decision isn't obvious. Options:

Profile both implementations with real data
Use hash set neighbors (O(1) edge query + O(degree) iteration)
Consider dual representation for critical code paths

Edge Case 2: Very Small Graphs

For |V| < 100, both representations use negligible memory. Prefer:

Matrix for simplicity if algorithm is naturally matrix-based
List for consistency with larger graphs in the same codebase
Whatever your team is more familiar with

Watch Out For These Situations

•Hidden quadratic behavior: Even with lists, algorithms can be accidentally O(|V|²) if you're not careful
•Memory fragmentation: Many small adjacency lists can fragment heap memory
•Cache thrashing: Random access patterns defeat both representations' cache optimization
•Growing graphs: Matrices can't grow efficiently—preallocate for expected max or use lists
•Concurrent access: Different representations have different locking requirements
•Serialization needs: Matrices serialize trivially; lists require more complex formats

Edge Case 3: Bipartite Graphs

Bipartite graphs with vertex sets U and W can use a specialized |U| × |W| matrix (rectangular), which is more memory-efficient than a full (|U|+|W|)² matrix. This is common in:

User-item recommendation systems
Matching problems
Two-mode network analysis

Edge Case 4: Multi-graphs and Hypergraphs

Neither basic representation handles multi-edges or hyperedges well:

Multi-edges: Use list with edge multiplicity, or adjacency dict with edge lists
Hyperedges: Use incidence matrix or specialized hypergraph structures

When In Doubt, Benchmark

For performance-critical systems in the gray zone (moderate density, mixed operations, or unusual access patterns), theory only gets you so far. Implement both representations behind a common interface, run benchmarks with realistic data, and let the measurements decide. The best engineers prototype before committing.

Implementation Checklist

Before finalizing your implementation, walk through this checklist:

Pre-Implementation Checklist

•☐ Counted or estimated |V| and |E| — Know your scale
•☐ Calculated density — Sparse (<10%) or dense (>25%)?
•☐ Identified dominant operations — What does your algorithm do most?
•☐ Considered dynamism — Will the graph grow or change?
•☐ Estimated memory usage — Will it fit in available RAM?
•☐ Matched algorithm to representation — Using the right technique for your structure?
•☐ Planned for edge cases — Self-loops? Multi-edges? Disconnected vertices?

Implementation Best Practices

•Abstract the interface — Define a Graph interface so you can swap representations later
•Document the choice — Leave a comment explaining why you chose this representation
•Validate inputs — Check for out-of-bounds vertex indices
•Handle missing edges gracefully — Return 0/null/Infinity appropriately
•Consider immutability — Immutable graphs enable safe concurrent access
•Use typed arrays when possible — Uint32Array or Float64Array beat generic arrays
•Preallocate when size is known — Avoid resizing costs

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
// Define an interface that works for any representation
interface Graph<V = number, E = number> {
    // Core queries
    vertexCount(): number;
    edgeCount(): number;
    hasVertex(v: V): boolean;
    hasEdge(from: V, to: V): boolean;
    getEdgeWeight(from: V, to: V): E | null;
    
    // Iteration
    vertices(): Iterable<V>;
    edges(): Iterable<[V, V, E]>;
    neighbors(v: V): Iterable<V>;
    weightedNeighbors(v: V): Iterable<[V, E]>;
    
    // Modification (if supported)
    addVertex(v: V): void;
    removeVertex(v: V): void;
    addEdge(from: V, to: V, weight: E): void;
    removeEdge(from: V, to: V): void;
    
    // Utility
    degree(v: V): number;
    inDegree?(v: V): number;  // For directed graphs
    outDegree?(v: V): number;
}
 
// Now implement both representations behind this interface
class AdjacencyListGraph implements Graph { /* ... */ }
class AdjacencyMatrixGraph implements Graph { /* ... */ }
 
// Your algorithms work with the interface, not the implementation
function dijkstra(graph: Graph, source: number): Map<number, number> {
    // This works regardless of underlying representation!
    for (const [neighbor, weight] of graph.weightedNeighbors(source)) {
        // ...
    }
}

Summary: The Complete Decision Framework

You now have a complete toolkit for making informed graph representation decisions. Let's consolidate the key principles:

Key Takeaways

•Default to adjacency list — It's correct for ~95% of real-world applications.
•Always characterize your graph — Know |V|, |E|, density, and dynamism before deciding.
•Match representation to operations — Neighbor-heavy → list; edge-query-heavy → matrix.
•Use the decision tree — A quick path for common cases saves analysis time.
•Know when matrices win — Small, static, dense graphs with Floyd-Warshall, correlation/similarity, or complete graphs.
•Abstract your interface — Allow representation swapping without algorithm changes.
•Benchmark when uncertain — In the gray zone, measurements beat theory.

Final Quick Reference
Criterion	Use Adjacency List	Use Adjacency Matrix
Graph Size	\|V\| > 5,000	\|V\| < 5,000
Density	< 10%	25%
Dynamism	Dynamic (grows/shrinks)	Static only
Dominant Operation	Neighbor iteration	Edge queries
Memory	Space-constrained	Memory abundant
Algorithm Type	BFS, DFS, Dijkstra, most	Floyd-Warshall, matrix power
Real-World Graphs	Almost always	Rarely

Module Complete!

You've mastered graph representation trade-offs—one of the most important concepts in graph algorithms. You understand space complexity, time complexity for every operation, the critical role of density, and how to systematically choose the right representation.

With this foundation, you're ready to tackle the full range of graph algorithms knowing that your choice of representation is informed, justified, and optimal for your specific needs.

Module Complete

Congratulations! You've completed the Graph Representation Trade-offs module. You can now make informed decisions about adjacency matrices versus adjacency lists, justify those decisions with precise analysis, and recognize the rare cases where the default (adjacency list) doesn't apply. This knowledge will serve you throughout your graph algorithm journey.

Choosing the Right Representation

The Decision Framework

What You Will Learn

The Five-Step Decision Process

For any graph problem, follow this systematic process:

Step 1: Characterize the Graph

What is |V| (vertex count)?
What is |E| (edge count)?
Compute density = |E| / max_edges
Is the graph static (never changes) or dynamic (edges/vertices added/removed)?
Is it directed or undirected?
Is it weighted or unweighted?

Step 2: Identify Dominant Operations

Ask: which operations does my algorithm perform most frequently?

Heavy edge querying → favor matrix
Heavy neighbor iteration → favor list
Heavy modification → consider implementation variants
Mixed operations → analyze relative frequencies

Step 3: Apply Quick Heuristics

•If density < 10% → Use adjacency list (almost always correct)
•If density > 25% AND |V| < 5,000 → Consider adjacency matrix
•If graph is dynamic → Use adjacency list (matrices can't grow efficiently)
•If algorithm is traversal-based (BFS, DFS, Dijkstra) → Use adjacency list
•If algorithm needs O(1) edge queries constantly → Consider matrix or hash-set neighbors
•If |V| > 10,000 → Use adjacency list unless you have a very specific reason not to

Step 4: Consider Memory Constraints

Calculate exact memory usage for each option
Matrix: |V|² × bytes_per_cell
List: |V| × overhead_per_vertex + |E| × bytes_per_edge
Consider cache effects for your access patterns

Step 5: Prototype and Measure (if critical)

For performance-critical systems:

Implement both representations
Benchmark with realistic data
Profile actual cache behavior
Choose based on measured performance, not just theory

The 95% Rule

The Visual Decision Tree

For quick decisions, follow this decision tree. Start at the top and follow branches based on your answers:

                    ┌─────────────────────┐
                    │ Is |V| > 10,000?    │
                    └──────────┬──────────┘
                               │
              ┌────────────────┴────────────────┐
              │ YES                             │ NO
              ▼                                 ▼
   ┌───────────────────┐           ┌───────────────────────┐
   │ Use Adjacency     │           │ Is the graph dynamic  │
   │ List (always)     │           │ (vertices/edges       │
   │                   │           │  added/removed)?      │
   └───────────────────┘           └───────────┬───────────┘
                                               │
                          ┌────────────────────┴────────────────────┐
                          │ YES                                     │ NO
                          ▼                                         ▼
               ┌───────────────────┐               ┌────────────────────────┐
               │ Use Adjacency     │               │ Is density > 25%?      │
               │ List              │               │                        │
               └───────────────────┘               └───────────┬────────────┘
                                                               │
                                      ┌────────────────────────┴─────────────────────────┐
                                      │ YES                                              │ NO
                                      ▼                                                  ▼
                     ┌─────────────────────────────────┐            ┌────────────────────────┐
                     │ Does algorithm need O(1) edge   │            │ Use Adjacency List     │
                     │ queries more than O(degree)     │            │                        │
                     │ neighbor iteration?             │            └────────────────────────┘
                     └───────────────┬─────────────────┘
                                     │
                    ┌────────────────┴────────────────┐
                    │ YES                             │ NO
                    ▼                                 ▼
         ┌───────────────────┐           ┌───────────────────┐
         │ Use Adjacency     │           │ Use Adjacency     │
         │ Matrix            │           │ List              │
         └───────────────────┘           └───────────────────┘

Notice the Pattern

Common Scenarios: Quick Reference Guide

Here's a quick reference for common graph problems and their optimal representations:

Representation Choice by Problem Type
Problem/Algorithm	Typical Density	Dominant Operation	Recommendation
Social Network Analysis	<0.01%	Neighbor iteration	Adjacency List
Web Crawling/PageRank	<0.001%	Neighbor iteration	Adjacency List
Road Network Navigation	<0.01%	Neighbor iteration	Adjacency List
BFS/DFS Traversal	Any	Neighbor iteration	Adjacency List
Dijkstra's Algorithm	Usually sparse	Neighbor iteration	Adjacency List
Bellman-Ford	Usually sparse	Edge iteration	Adjacency List
Topological Sort	Usually sparse	Neighbor iteration	Adjacency List
Connected Components	Usually sparse	Neighbor iteration	Adjacency List
Minimum Spanning Tree	Usually sparse	Edge iteration	Adjacency List
Floyd-Warshall APSP	Any	Edge queries O(V³)	Adjacency Matrix
Complete Graph K_n	100%	All operations	Adjacency Matrix
Small Dense Subproblem	25%, \|V\|<1000	Mixed	Adjacency Matrix
Similarity/Correlation	100%	Edge queries	Adjacency Matrix (it IS one)
Dynamic Connectivity	Varies	Edge modification	Adjacency List + Union-Find

Always Use Adjacency List

•Social media graphs (billions of users)
•Web graphs (billions of pages)
•Road networks (millions of intersections)
•Knowledge graphs (millions of entities)
•Dependency graphs (packages, modules)
•Citation networks (papers, patents)
•Any dynamic graph that grows
•Any graph loaded from external data

Consider Adjacency Matrix

•Floyd-Warshall all-pairs shortest paths
•Tournament scheduling (complete graph)
•Small clique detection subproblems
•Similarity/correlation matrices
•Graph powers (A², A³, etc.)
•Small static graphs (|V| < 500)
•Matrix-based graph algorithms
•Theoretical analysis / proofs

Case Study: Building a Friend Recommendation System

Let's apply our decision framework to a real engineering scenario.

The Problem:

You're building a friend recommendation system for a social network. Given a user, recommend "friends of friends" who aren't already friends. The network has:

10 million users
Average 200 friends per user
Users added continuously
Friendships created/removed frequently

Step 1: Characterize the Graph

|V| = 10,000,000
|E| ≈ (10M × 200) / 2 = 1,000,000,000 edges
Density = 1B / (10M × 10M / 2) ≈ 0.00002% — extremely sparse
Dynamic: users and friendships constantly changing
Undirected (friendship is mutual)
Unweighted

Step 2: Identify Dominant Operations

For friend-of-friend recommendations:

for each friend F of user U:
    for each friend FF of F:
        if FF not in U.friends and FF != U:
            recommend.add(FF)

Dominant operation: neighbor iteration (iterating friends of friends)
Secondary operation: membership check (is FF already a friend?)
Edge queries: rare (only for duplicate checking, can use a Set)

Step 3: Apply Heuristics

Density < 10%? Yes (0.00002%) → List
Graph dynamic? Yes → List
|V| > 10,000? Yes (10M) → List

Every heuristic points to adjacency list.

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
interface SocialGraph {
    // Adjacency list representation
    adjacency: Map<string, Set<string>>;  // userId -> Set of friend userIds
}
 
function recommendFriends(
    graph: SocialGraph, 
    userId: string, 
    maxRecommendations: number = 10
): string[] {
    const userFriends = graph.adjacency.get(userId);
    if (!userFriends) return [];
    
    // Count how many mutual friends each potential recommendation has
    const mutualCount = new Map<string, number>();
    
    // O(degree(user) × average_degree) - efficient with list representation
    for (const friend of userFriends) {  // Iterate neighbors: O(degree)
        const friendsOfFriend = graph.adjacency.get(friend);
        if (!friendsOfFriend) continue;
        
        for (const fof of friendsOfFriend) {  // Iterate neighbors again
            // Skip if already friend or self
            if (fof === userId || userFriends.has(fof)) continue;  // O(1) Set lookup
            
            mutualCount.set(fof, (mutualCount.get(fof) ?? 0) + 1);
        }
    }
    
    // Sort by mutual friend count, return top recommendations
    return [...mutualCount.entries()]
        .sort((a, b) => b[1] - a[1])
        .slice(0, maxRecommendations)
        .map(([userId, _count]) => userId);
}
 
// Memory analysis:
// Matrix would need: 10M × 10M × 1 byte = 100 TB (IMPOSSIBLE)
// List uses: ~10M × overhead + 2B × ~8 bytes ≈ 16 GB (manageable)

Decision: Adjacency List

Case Study: All-Pairs Shortest Paths in a Small Network

Now let's examine a scenario where the matrix might win.

The Problem:

You're computing latency between all pairs of servers in a data center network:

500 servers
Nearly full mesh connectivity (for redundancy)
About 100,000 connections
Network is static (reconfigure rarely)
Need all-pairs shortest paths for routing decisions

Step 1: Characterize the Graph

|V| = 500
|E| = 100,000
Max edges = 500 × 499 / 2 = 124,750
Density = 100,000 / 124,750 ≈ 80% — very dense
Static: rarely changes
Undirected (latency is symmetric)
Weighted (latency in milliseconds)

Step 2: Identify Dominant Operations

For all-pairs shortest paths:

Floyd-Warshall: O(|V|³) edge queries
Output: |V|² distance values

Dominant operation: constant edge queries in the innermost loop.

Step 3: Apply Heuristics

Density > 25%? Yes (80%) → Consider matrix
|V| < 10,000? Yes (500) → Matrix is feasible
Graph static? Yes → Matrix OK
Algorithm needs O(1) edge queries? Yes (Floyd-Warshall) → Matrix favored

This is one of the rare cases where matrix is optimal!

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
function floydWarshall(latencyMatrix: number[][]): number[][] {
    const n = latencyMatrix.length;
    
    // Initialize distance matrix (copy of input)
    // Already an adjacency matrix - no conversion needed!
    const dist = latencyMatrix.map(row => [...row]);
    
    // Set self-distances to 0, unreachable to Infinity
    for (let i = 0; i < n; i++) {
        dist[i][i] = 0;
        for (let j = 0; j < n; j++) {
            if (i !== j && dist[i][j] === 0) {
                dist[i][j] = Infinity;  // No direct edge
            }
        }
    }
    
    // Floyd-Warshall: O(V³)
    // Every operation in the inner loop is O(1) thanks to matrix representation
    for (let k = 0; k < n; k++) {
        for (let i = 0; i < n; i++) {
            for (let j = 0; j < n; j++) {
                // This edge query is O(1) with matrix
                // Would be O(degree) with naive adjacency list
                if (dist[i][k] + dist[k][j] < dist[i][j]) {
                    dist[i][j] = dist[i][k] + dist[k][j];
                }
            }
        }
    }
    
    return dist;
}
 
// Memory analysis:
// Matrix: 500 × 500 × 8 bytes (float64) = 2 MB (trivial)
// Output is also 500 × 500 = inherently matrix-shaped
 
// Performance analysis:
// With matrix: 500³ × O(1) = 125 million simple operations
// With list: Would need edge lookup in inner loop - much slower

Decision: Adjacency Matrix

Edge Cases and Special Considerations

Not every decision is clear-cut. Here are situations that require careful thought:

Edge Case 1: Moderate Density, Mixed Operations

When density is 10-25% and your algorithm both queries edges and iterates neighbors frequently, the decision isn't obvious. Options:

Profile both implementations with real data
Use hash set neighbors (O(1) edge query + O(degree) iteration)
Consider dual representation for critical code paths

Edge Case 2: Very Small Graphs

For |V| < 100, both representations use negligible memory. Prefer:

Matrix for simplicity if algorithm is naturally matrix-based
List for consistency with larger graphs in the same codebase
Whatever your team is more familiar with

Watch Out For These Situations

•Hidden quadratic behavior: Even with lists, algorithms can be accidentally O(|V|²) if you're not careful
•Memory fragmentation: Many small adjacency lists can fragment heap memory
•Cache thrashing: Random access patterns defeat both representations' cache optimization
•Growing graphs: Matrices can't grow efficiently—preallocate for expected max or use lists
•Concurrent access: Different representations have different locking requirements
•Serialization needs: Matrices serialize trivially; lists require more complex formats

Edge Case 3: Bipartite Graphs

Bipartite graphs with vertex sets U and W can use a specialized |U| × |W| matrix (rectangular), which is more memory-efficient than a full (|U|+|W|)² matrix. This is common in:

User-item recommendation systems
Matching problems
Two-mode network analysis

Edge Case 4: Multi-graphs and Hypergraphs

Neither basic representation handles multi-edges or hyperedges well:

Multi-edges: Use list with edge multiplicity, or adjacency dict with edge lists
Hyperedges: Use incidence matrix or specialized hypergraph structures

When In Doubt, Benchmark

Implementation Checklist

Before finalizing your implementation, walk through this checklist:

Pre-Implementation Checklist

•☐ Counted or estimated |V| and |E| — Know your scale
•☐ Calculated density — Sparse (<10%) or dense (>25%)?
•☐ Identified dominant operations — What does your algorithm do most?
•☐ Considered dynamism — Will the graph grow or change?
•☐ Estimated memory usage — Will it fit in available RAM?
•☐ Matched algorithm to representation — Using the right technique for your structure?
•☐ Planned for edge cases — Self-loops? Multi-edges? Disconnected vertices?

Implementation Best Practices

•Abstract the interface — Define a Graph interface so you can swap representations later
•Document the choice — Leave a comment explaining why you chose this representation
•Validate inputs — Check for out-of-bounds vertex indices
•Handle missing edges gracefully — Return 0/null/Infinity appropriately
•Consider immutability — Immutable graphs enable safe concurrent access
•Use typed arrays when possible — Uint32Array or Float64Array beat generic arrays
•Preallocate when size is known — Avoid resizing costs

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
// Define an interface that works for any representation
interface Graph<V = number, E = number> {
    // Core queries
    vertexCount(): number;
    edgeCount(): number;
    hasVertex(v: V): boolean;
    hasEdge(from: V, to: V): boolean;
    getEdgeWeight(from: V, to: V): E | null;
    
    // Iteration
    vertices(): Iterable<V>;
    edges(): Iterable<[V, V, E]>;
    neighbors(v: V): Iterable<V>;
    weightedNeighbors(v: V): Iterable<[V, E]>;
    
    // Modification (if supported)
    addVertex(v: V): void;
    removeVertex(v: V): void;
    addEdge(from: V, to: V, weight: E): void;
    removeEdge(from: V, to: V): void;
    
    // Utility
    degree(v: V): number;
    inDegree?(v: V): number;  // For directed graphs
    outDegree?(v: V): number;
}
 
// Now implement both representations behind this interface
class AdjacencyListGraph implements Graph { /* ... */ }
class AdjacencyMatrixGraph implements Graph { /* ... */ }
 
// Your algorithms work with the interface, not the implementation
function dijkstra(graph: Graph, source: number): Map<number, number> {
    // This works regardless of underlying representation!
    for (const [neighbor, weight] of graph.weightedNeighbors(source)) {
        // ...
    }
}

Summary: The Complete Decision Framework

You now have a complete toolkit for making informed graph representation decisions. Let's consolidate the key principles:

Key Takeaways

•Default to adjacency list — It's correct for ~95% of real-world applications.
•Always characterize your graph — Know |V|, |E|, density, and dynamism before deciding.
•Match representation to operations — Neighbor-heavy → list; edge-query-heavy → matrix.
•Use the decision tree — A quick path for common cases saves analysis time.
•Know when matrices win — Small, static, dense graphs with Floyd-Warshall, correlation/similarity, or complete graphs.
•Abstract your interface — Allow representation swapping without algorithm changes.
•Benchmark when uncertain — In the gray zone, measurements beat theory.

Final Quick Reference
Criterion	Use Adjacency List	Use Adjacency Matrix
Graph Size	\|V\| > 5,000	\|V\| < 5,000
Density	< 10%	25%
Dynamism	Dynamic (grows/shrinks)	Static only
Dominant Operation	Neighbor iteration	Edge queries
Memory	Space-constrained	Memory abundant
Algorithm Type	BFS, DFS, Dijkstra, most	Floyd-Warshall, matrix power
Real-World Graphs	Almost always	Rarely

Module Complete!

With this foundation, you're ready to tackle the full range of graph algorithms knowing that your choice of representation is informed, justified, and optimal for your specific needs.

Module Complete