Data Structures & AlgorithmsGraph Representation — Adjacency Matrix

Graph Representation — Adjacency Matrix

LevelIntermediate

Duration60 mins

TopicGraph Representation — Adjacency Matrix

4 / 4

When Matrices Are Appropriate

Making the Right Representation Choice

We've now explored the adjacency matrix in depth: its simple 2D array structure, its O(V²) space cost, and its O(1) edge lookup advantage. The question that matters in practice is: when should you actually use an adjacency matrix?

This isn't a theoretical exercise. Choosing the wrong representation can mean algorithms that run in seconds versus hours, or systems that crash versus scale gracefully. This page synthesizes everything we've learned into practical decision-making guidance.

By the end of this page, you'll have clear heuristics for when adjacency matrices are the right choice, when to avoid them, and how to recognize the characteristics that favor one representation over another.

What You Will Learn

By the end of this page, you will have a systematic decision framework for choosing adjacency matrices, understand specific use cases where matrices excel, recognize warning signs that suggest alternative representations, and be able to justify your representation choices with clear reasoning.

The Decision Framework

When facing a graph problem, use this systematic framework to decide on representation:

Step 1: Assess the Graph Size

Calculate V² and determine if it fits in available memory with room to spare.

V ≤ 1,000: Matrix is almost always fine (~4 MB for int matrix)
V ≤ 5,000: Matrix is manageable (~100 MB)
V ≤ 10,000: Matrix is possible (~400 MB) but consider alternatives
V > 10,000: Matrix becomes problematic (>400 MB), strongly prefer lists
V > 50,000: Matrix is impractical (>10 GB), avoid

Step 2: Assess Graph Density

Estimate E/V² (edge density). Dense graphs (density > 10-20%) make better use of matrix space.

Step 3: Identify Dominant Operations

What operations will you perform most frequently? Matrix favors edge queries; lists favor neighbor enumeration.

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
Decision Flowchart for Graph Representation:
 
                    START
                      │
                      ▼
              ┌───────────────┐
              │   V > 10,000? │
              └───────┬───────┘
                      │
          ┌───────────┴───────────┐
          ▼ YES                   ▼ NO
   ┌─────────────┐        ┌───────────────┐
   │ Use         │        │ E > V²/10?    │
   │ Adjacency   │        │ (density >10%)│
   │ List        │        └───────┬───────┘
   └─────────────┘                │
                      ┌───────────┴───────────┐
                      ▼ YES                   ▼ NO
              ┌─────────────┐        ┌────────────────────┐
              │ Matrix is   │        │ Primary operation? │
              │ space-      │        └──────────┬─────────┘
              │ efficient   │                   │
              └──────┬──────┘        ┌──────────┴──────────┐
                     │               ▼                     ▼
                     │        Edge queries          Traversals
                     │        (existence,           (BFS, DFS,
                     │         weights)             neighbors)
                     │               │                     │
                     ▼               ▼                     ▼
              ┌─────────────┐ ┌─────────────┐      ┌─────────────┐
              │ Use Matrix  │ │ Use Matrix  │      │ Use List    │
              └─────────────┘ └─────────────┘      └─────────────┘

The Quick Heuristic

If in doubt, use this quick rule: 'Matrix for small dense graphs or edge-query algorithms; lists for everything else.' Most real-world graphs are sparse and large, which pushes toward lists. But when matrices work, they work exceptionally well.

Ideal Use Cases for Adjacency Matrices

Let's examine specific scenarios where adjacency matrices are the clear winner:

Use Case 1: Complete or Near-Complete Graphs

When most possible edges exist (tournaments, complete bipartite graphs, fully-connected networks), the matrix uses its space efficiently. Example: A round-robin tournament with 100 teams has 100×99/2 = 4,950 edges—nearly half the matrix cells.

Use Case 2: All-Pairs Algorithms

Floyd-Warshall (all-pairs shortest paths), computing path existence matrices, and transitive closure are inherently matrix operations. The output is a V×V matrix, so you're paying O(V²) space regardless.

Use Case 3: Matrix-Based Graph Analysis

Spectral graph theory, eigenvalue analysis, graph neural networks operating on adjacency matrices—these mathematical approaches work directly with the matrix structure.

Strong Indicators for Matrix Representation

•Dense graphs — Edge density > 20%; most vertex pairs are connected
•Small vertex counts — V ≤ 5,000 where V² easily fits in memory
•All-pairs computations — Output is naturally V×V (shortest paths, connectivity)
•Frequent edge existence queries — Algorithms that check 'is (i,j) an edge?' often
•Matrix algebra operations — Eigenvalues, matrix powers, spectral methods
•Complement graph operations — Finding non-edges is O(1) with matrices
•Static graphs — Graph structure doesn't change; initialization cost is amortized
•Real-time constraints — Need guaranteed O(1) lookup, not average O(1)

Real-World Applications Suited for Adjacency Matrices
Application	Why Matrix Works	Typical Size
Distance matrix for TSP	Need all pairwise distances	V < 1,000
Network flow analysis	Floyd-Warshall for all-pairs paths	V < 1,000
Tournament scheduling	Complete or near-complete graph	V < 500
Correlation matrices	Every pair has a value	V < 10,000
Small game state graphs	Dense state transitions	V < 5,000
Circuit analysis	Component connectivity	V < 1,000
Protein interaction (small datasets)	Dense interaction networks	V < 2,000

When to Avoid Adjacency Matrices

Just as important as knowing when to use matrices is recognizing when they're inappropriate:

Avoid When: Large, Sparse Graphs

The overwhelming majority of real-world graphs fall into this category. Social networks, road maps, the web, dependency graphs—all have millions of vertices but each vertex connects to only a small subset. A matrix would waste 99%+ of its space.

Avoid When: Graph Structure Changes Dynamically

Adding or removing vertices is expensive with matrices—you need to resize the entire 2D array. If vertices frequently come and go, lists are far more flexible.

Avoid When: Memory Is Constrained

Embedded systems, mobile apps, or serverless functions with memory limits can't afford O(V²) space for non-trivial graphs.

Warning Signs: Don't Use Matrix

•V > 50,000 — Memory requirements exceed typical RAM
•Sparse graphs (E << V²) — Trees, planar graphs, k-regular graphs with small k
•Dynamic vertex sets — Vertices added/removed frequently
•Traversal-heavy algorithms — BFS, DFS, Dijkstra iterate over neighbors, not edge queries
•Memory-constrained environments — Embedded, mobile, serverless
•Streaming graphs — Edges arrive over time, graph grows unboundedly
•Scale-free networks — Social networks with power-law degree distribution

The Social Network Anti-Pattern

Never use an adjacency matrix for social network-scale graphs. With millions of users, a matrix would require terabytes of RAM. Even a 'small' social network of 100,000 users would need 40-80 GB for a matrix. This is a classic example where the theoretical elegance of matrices collides with practical reality.

The Sparse Graph Reality:

Most graphs in practice are sparse. Consider these real-world edge densities:

Road networks: Average degree ~4, so E ≈ 2V. Density = 2V/V² = 2/V → nearly 0%
Social networks: Average degree ~100-500, so E ≈ 50V-250V. Density = 0.005%-0.025%
Web graph: Average degree ~10-50. Density < 0.01%
Package dependencies: Average degree ~10-100. Density < 0.1%

For these graphs, matrices waste 99%+ of their space. Lists are the clear choice.

Algorithm-Specific Representation Guidance

Different graph algorithms have different performance profiles depending on representation. Here's algorithm-by-algorithm guidance:

Traversals (BFS, DFS):

These algorithms iterate over each vertex's neighbors. With a matrix, finding neighbors is O(V) per vertex—scan the entire row. With a list, it's O(degree). For sparse graphs, lists can be V/degree times faster.

Recommendation: Lists for sparse graphs; either for dense graphs.

Single-Source Shortest Path (Dijkstra, Bellman-Ford):

Dijkstra relaxes edges from the current vertex's neighbors. Edge weight lookup is needed. Lists with O(1) neighbor access beat matrices.

Recommendation: Lists.

Algorithm Representation Recommendations
Algorithm	Key Operations	Best Representation	Reason
BFS / DFS	Iterate neighbors	List	O(degree) vs O(V) per vertex
Dijkstra's	Iterate neighbors + edge weights	List	Neighbor iteration dominates
Bellman-Ford	Iterate all edges	List	Lists store only edges, not non-edges
Floyd-Warshall	All-pairs distance queries	Matrix	Algorithm is matrix-based
Prim's MST	Iterate neighbors	List	Similar to Dijkstra
Kruskal's MST	Sort edges, union-find	Edge List	Doesn't need fast lookup
Topological Sort	Iterate neighbors	List	Traversal-based
Tarjan's SCC	DFS-based	List	Traversal-based
Triangle Counting	Check edge existence for triplets	Matrix	O(1) edge checks dominate
Clique Finding	Many edge existence checks	Matrix	Edge checks are inner loop
Graph Coloring	Check neighbor colors	Either	Depends on implementation
Bipartite Check	BFS/DFS traversal	List	Traversal-based

When Both Work

For small graphs (V < 1,000), the absolute time difference between representations is usually negligible—milliseconds at most. Use whichever is easier to implement. The representation choice only becomes critical at scale or in performance-critical inner loops.

Real-World Examples and Case Studies

Let's examine real-world scenarios and determine the appropriate representation:

Example 1: Airline Route Planning

A company manages 500 airports with ~2,000 direct routes.

V = 500, E = 2,000
Matrix size: 500² = 250,000 cells ≈ 1 MB
List size: 500 + 2,000 = 2,500 entries ≈ 20 KB

Operation analysis: Route queries ("is there a direct flight?") are common for pricing. Lists would require scanning 4 routes on average. Matrix gives O(1).

Decision: Matrix is viable (small graph) and useful for route queries. Could use list for traversals.

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
/**
 * Airline Route Planning System
 * 
 * Use case analysis:
 * - 500 airports (vertices)
 * - 2,000 routes (edges)
 * - Frequent queries: "Is there a direct flight from A to B?"
 * - Occasional: "Find all connecting flights from A"
 * 
 * Decision: Use matrix because:
 * 1. V² = 250,000 (fits easily in memory)
 * 2. Edge queries are frequent and need O(1)
 * 3. Can afford the O(V) neighbor iteration occasionally
 */
 
class AirlineNetwork {
    // Matrix stores flight times (or Infinity for no route)
    private routes: number[][];
    private airportIndex: Map<string, number>;
    
    constructor(airports: string[]) {
        const V = airports.length;
        this.routes = Array.from(
            { length: V }, 
            () => Array(V).fill(Infinity)
        );
        
        this.airportIndex = new Map();
        airports.forEach((code, i) => this.airportIndex.set(code, i));
    }
    
    addRoute(from: string, to: string, flightTime: number): void {
        const i = this.airportIndex.get(from)!;
        const j = this.airportIndex.get(to)!;
        this.routes[i][j] = flightTime;  // O(1)
    }
    
    // Primary operation: O(1) direct route check
    hasDirectFlight(from: string, to: string): boolean {
        const i = this.airportIndex.get(from)!;
        const j = this.airportIndex.get(to)!;
        return this.routes[i][j] !== Infinity;  // O(1)
    }
    
    // Can also run Floyd-Warshall for all-pairs shortest paths
    computeAllShortestPaths(): number[][] {
        // Floyd-Warshall works directly on this matrix
        // (implementation would go here)
        return this.routes;
    }
}

Example 2: Facebook Friend Recommendations

Facebook has ~3 billion users with average 500 friends each.

V = 3,000,000,000, E ≈ 750,000,000,000 (750 billion)
Matrix size: V² = 9 × 10¹⁸ cells ≈ 9 exabytes (impossible)
List size: V + 2E ≈ 1.5 trillion entries ≈ 6 TB (distributed, but feasible)

Decision: Adjacency list (distributed) is the only option. Matrix is physically impossible.

Example 3: Traveling Salesman Problem (TSP)

A delivery company optimizes routes between 100 stops.

V = 100, E = complete graph = 100×99/2 = 4,950 edges
Matrix size: 10,000 cells ≈ 80 KB
The TSP algorithm needs all pairwise distances

Decision: Matrix is perfect. Dense graph, small size, all-pairs access pattern.

Problem Size Sanity Check

Always compute V² before choosing a matrix. A million-vertex graph sounds manageable until you realize V² = 1 trillion. Multiply by bytes per cell and compare to your available RAM. This quick calculation often immediately rules out matrices.

Hybrid and Specialized Approaches

In complex systems, you may need the advantages of both representations. Here are sophisticated approaches:

Approach 1: Dual Representation

Maintain both an adjacency matrix and adjacency list. Use the matrix for edge queries, the list for traversals. Cost: ~2× memory, but O(1) for both key operations.

Approach 2: Cached Edge Queries

Use an adjacency list as primary representation, but cache frequently queried edges in a hash set. Adapts to access patterns at runtime.

Approach 3: Sparse Matrix Representations

For sparse graphs that need matrix operations (e.g., spectral analysis), use sparse matrix formats:

COO (Coordinate): Store (row, col, value) triples
CSR (Compressed Sparse Row): Efficient row iteration
CSC (Compressed Sparse Column): Efficient column iteration

These provide matrix semantics with O(E) space.

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
62
63
64
65
/**
 * Compressed Sparse Row (CSR) format for sparse graphs.
 * 
 * Provides matrix-like access patterns with O(V + E) space.
 * Used in scientific computing, graph ML, and sparse matrix libraries.
 */
class CSRGraph {
    // The adjacency list, but in CSR format for cache efficiency
    private values: number[];    // Edge weights (length = E)
    private colIndex: number[];  // Column indices (length = E)  
    private rowPtr: number[];    // Row start pointers (length = V + 1)
    
    constructor(vertices: number, edges: [number, number, number][]) {
        this.rowPtr = new Array(vertices + 1).fill(0);
        
        // Count edges per row
        for (const [from, _to, _weight] of edges) {
            this.rowPtr[from + 1]++;
        }
        
        // Cumulative sum to get row pointers
        for (let i = 1; i <= vertices; i++) {
            this.rowPtr[i] += this.rowPtr[i - 1];
        }
        
        // Fill in edges
        this.values = new Array(edges.length);
        this.colIndex = new Array(edges.length);
        const tempRowPtr = [...this.rowPtr];
        
        for (const [from, to, weight] of edges) {
            const idx = tempRowPtr[from]++;
            this.values[idx] = weight;
            this.colIndex[idx] = to;
        }
    }
    
    /**
     * Get neighbors of vertex v.
     * Time: O(degree(v)) — same as adjacency list
     */
    getNeighbors(v: number): { vertex: number; weight: number }[] {
        const neighbors = [];
        for (let i = this.rowPtr[v]; i < this.rowPtr[v + 1]; i++) {
            neighbors.push({
                vertex: this.colIndex[i],
                weight: this.values[i]
            });
        }
        return neighbors;
    }
    
    /**
     * Check if edge exists.
     * Time: O(degree(v)) — must scan row (unlike O(1) for dense matrix)
     * But O(log degree) with binary search if columns are sorted.
     */
    hasEdge(from: number, to: number): boolean {
        for (let i = this.rowPtr[from]; i < this.rowPtr[from + 1]; i++) {
            if (this.colIndex[i] === to) return true;
        }
        return false;
    }
}
// CSR is used by: SciPy, NumPy, graph neural network libraries (PyG, DGL)

Industry Standard Formats

CSR (Compressed Sparse Row) is the industry standard for sparse matrix operations. Libraries like SciPy, PyTorch Geometric, and graph databases use CSR or variants. It provides O(V + E) space with efficient row iteration—a best-of-both-worlds approach for many applications.

Decision Checklist

Before finalizing your representation choice, run through this checklist:

Memory Check:

□ Calculated V² × bytes per cell □ Confirmed this fits in available RAM (with headroom) □ Considered cache implications for large matrices

Density Check:

□ Estimated E / V² (edge density) □ If < 5%, strongly favor lists □ If > 50%, matrix uses space well

Operation Check:

□ Identified the dominant operation(s) □ Edge existence checks → favor matrix □ Neighbor iteration → favor lists

Algorithm Check:

□ Reviewed algorithm requirements □ Matrix-based algorithms (Floyd-Warshall) → require matrix □ Traversal-based algorithms (BFS, DFS) → favor lists

Choose Matrix When...

•✓ V ≤ 5,000 (V² ≤ 25 million)
•✓ Graph is dense (E > V²/5)
•✓ Frequent edge existence queries
•✓ Running Floyd-Warshall or matrix operations
•✓ Need guaranteed O(1) worst-case lookup
•✓ Graph is static (no vertex changes)
•✓ Working with complete graphs

Choose List When...

•✓ V > 10,000
•✓ Graph is sparse (E < V × log V)
•✓ Primary operation is neighbor enumeration
•✓ Running BFS, DFS, Dijkstra
•✓ Memory is constrained
•✓ Vertices are added/removed dynamically
•✓ Working with trees or near-trees

The Default Choice

If you're unsure, default to adjacency lists. They work well for the vast majority of practical graphs (which are sparse). Only switch to matrices when you have a specific reason—dense graph, edge-query-heavy algorithm, or matrix operations needed.

Summary: Choosing the Right Representation

We've completed our comprehensive study of adjacency matrices. Let's consolidate everything we've learned across this module:

Module Key Takeaways

•Adjacency matrices encode graphs as V×V arrays — Entry A[i][j] indicates edge from i to j; simple, elegant, powerful.
•Space cost is O(V²) — Fixed cost regardless of edge count; efficient for dense graphs, wasteful for sparse ones.
•Edge lookup is O(1) worst-case — Direct addressing guarantees constant-time edge queries, no matter what.
•Dense graphs and edge-query algorithms favor matrices — Floyd-Warshall, triangle counting, complement graphs.
•Large, sparse graphs demand alternatives — Social networks, road maps, web graphs must use adjacency lists.
•The decision is context-dependent — No single representation is 'best'; choose based on graph properties and operations.
•Hybrid approaches exist — CSR format, dual representation, and caching provide flexibility for complex systems.

What's Next:

We've mastered the adjacency matrix representation. The next module explores the alternative: adjacency lists—the representation that scales to billions of vertices and dominates real-world applications. Understanding both representations and when to use each is essential knowledge for any engineer working with graphs.

Module Complete

Congratulations! You've achieved mastery of adjacency matrix representation. You understand the structure (2D array), the trade-off (O(V²) space for O(1) lookup), and the decision criteria (dense/small graphs, edge-query algorithms). You're now equipped to make informed representation choices. Next: adjacency lists for the sparse graph world.

4 / 4

Loading learning content...

Data Structures & AlgorithmsGraph Representation — Adjacency Matrix

Graph Representation — Adjacency Matrix

LevelIntermediate

Duration60 mins

TopicGraph Representation — Adjacency Matrix

4 / 4

When Matrices Are Appropriate

Making the Right Representation Choice

What You Will Learn

The Decision Framework

When facing a graph problem, use this systematic framework to decide on representation:

Step 1: Assess the Graph Size

Calculate V² and determine if it fits in available memory with room to spare.

V ≤ 1,000: Matrix is almost always fine (~4 MB for int matrix)
V ≤ 5,000: Matrix is manageable (~100 MB)
V ≤ 10,000: Matrix is possible (~400 MB) but consider alternatives
V > 10,000: Matrix becomes problematic (>400 MB), strongly prefer lists
V > 50,000: Matrix is impractical (>10 GB), avoid

Step 2: Assess Graph Density

Estimate E/V² (edge density). Dense graphs (density > 10-20%) make better use of matrix space.

Step 3: Identify Dominant Operations

What operations will you perform most frequently? Matrix favors edge queries; lists favor neighbor enumeration.

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
Decision Flowchart for Graph Representation:
 
                    START
                      │
                      ▼
              ┌───────────────┐
              │   V > 10,000? │
              └───────┬───────┘
                      │
          ┌───────────┴───────────┐
          ▼ YES                   ▼ NO
   ┌─────────────┐        ┌───────────────┐
   │ Use         │        │ E > V²/10?    │
   │ Adjacency   │        │ (density >10%)│
   │ List        │        └───────┬───────┘
   └─────────────┘                │
                      ┌───────────┴───────────┐
                      ▼ YES                   ▼ NO
              ┌─────────────┐        ┌────────────────────┐
              │ Matrix is   │        │ Primary operation? │
              │ space-      │        └──────────┬─────────┘
              │ efficient   │                   │
              └──────┬──────┘        ┌──────────┴──────────┐
                     │               ▼                     ▼
                     │        Edge queries          Traversals
                     │        (existence,           (BFS, DFS,
                     │         weights)             neighbors)
                     │               │                     │
                     ▼               ▼                     ▼
              ┌─────────────┐ ┌─────────────┐      ┌─────────────┐
              │ Use Matrix  │ │ Use Matrix  │      │ Use List    │
              └─────────────┘ └─────────────┘      └─────────────┘

The Quick Heuristic

Ideal Use Cases for Adjacency Matrices

Let's examine specific scenarios where adjacency matrices are the clear winner:

Use Case 1: Complete or Near-Complete Graphs

Use Case 2: All-Pairs Algorithms

Use Case 3: Matrix-Based Graph Analysis

Spectral graph theory, eigenvalue analysis, graph neural networks operating on adjacency matrices—these mathematical approaches work directly with the matrix structure.

Strong Indicators for Matrix Representation

•Dense graphs — Edge density > 20%; most vertex pairs are connected
•Small vertex counts — V ≤ 5,000 where V² easily fits in memory
•All-pairs computations — Output is naturally V×V (shortest paths, connectivity)
•Frequent edge existence queries — Algorithms that check 'is (i,j) an edge?' often
•Matrix algebra operations — Eigenvalues, matrix powers, spectral methods
•Complement graph operations — Finding non-edges is O(1) with matrices
•Static graphs — Graph structure doesn't change; initialization cost is amortized
•Real-time constraints — Need guaranteed O(1) lookup, not average O(1)

Real-World Applications Suited for Adjacency Matrices
Application	Why Matrix Works	Typical Size
Distance matrix for TSP	Need all pairwise distances	V < 1,000
Network flow analysis	Floyd-Warshall for all-pairs paths	V < 1,000
Tournament scheduling	Complete or near-complete graph	V < 500
Correlation matrices	Every pair has a value	V < 10,000
Small game state graphs	Dense state transitions	V < 5,000
Circuit analysis	Component connectivity	V < 1,000
Protein interaction (small datasets)	Dense interaction networks	V < 2,000

When to Avoid Adjacency Matrices

Just as important as knowing when to use matrices is recognizing when they're inappropriate:

Avoid When: Large, Sparse Graphs

Avoid When: Graph Structure Changes Dynamically

Adding or removing vertices is expensive with matrices—you need to resize the entire 2D array. If vertices frequently come and go, lists are far more flexible.

Avoid When: Memory Is Constrained

Embedded systems, mobile apps, or serverless functions with memory limits can't afford O(V²) space for non-trivial graphs.

Warning Signs: Don't Use Matrix

•V > 50,000 — Memory requirements exceed typical RAM
•Sparse graphs (E << V²) — Trees, planar graphs, k-regular graphs with small k
•Dynamic vertex sets — Vertices added/removed frequently
•Traversal-heavy algorithms — BFS, DFS, Dijkstra iterate over neighbors, not edge queries
•Memory-constrained environments — Embedded, mobile, serverless
•Streaming graphs — Edges arrive over time, graph grows unboundedly
•Scale-free networks — Social networks with power-law degree distribution

The Social Network Anti-Pattern

The Sparse Graph Reality:

Most graphs in practice are sparse. Consider these real-world edge densities:

Road networks: Average degree ~4, so E ≈ 2V. Density = 2V/V² = 2/V → nearly 0%
Social networks: Average degree ~100-500, so E ≈ 50V-250V. Density = 0.005%-0.025%
Web graph: Average degree ~10-50. Density < 0.01%
Package dependencies: Average degree ~10-100. Density < 0.1%

For these graphs, matrices waste 99%+ of their space. Lists are the clear choice.

Algorithm-Specific Representation Guidance

Different graph algorithms have different performance profiles depending on representation. Here's algorithm-by-algorithm guidance:

Traversals (BFS, DFS):

Recommendation: Lists for sparse graphs; either for dense graphs.

Single-Source Shortest Path (Dijkstra, Bellman-Ford):

Dijkstra relaxes edges from the current vertex's neighbors. Edge weight lookup is needed. Lists with O(1) neighbor access beat matrices.

Recommendation: Lists.

Algorithm Representation Recommendations
Algorithm	Key Operations	Best Representation	Reason
BFS / DFS	Iterate neighbors	List	O(degree) vs O(V) per vertex
Dijkstra's	Iterate neighbors + edge weights	List	Neighbor iteration dominates
Bellman-Ford	Iterate all edges	List	Lists store only edges, not non-edges
Floyd-Warshall	All-pairs distance queries	Matrix	Algorithm is matrix-based
Prim's MST	Iterate neighbors	List	Similar to Dijkstra
Kruskal's MST	Sort edges, union-find	Edge List	Doesn't need fast lookup
Topological Sort	Iterate neighbors	List	Traversal-based
Tarjan's SCC	DFS-based	List	Traversal-based
Triangle Counting	Check edge existence for triplets	Matrix	O(1) edge checks dominate
Clique Finding	Many edge existence checks	Matrix	Edge checks are inner loop
Graph Coloring	Check neighbor colors	Either	Depends on implementation
Bipartite Check	BFS/DFS traversal	List	Traversal-based

When Both Work

Real-World Examples and Case Studies

Let's examine real-world scenarios and determine the appropriate representation:

Example 1: Airline Route Planning

A company manages 500 airports with ~2,000 direct routes.

V = 500, E = 2,000
Matrix size: 500² = 250,000 cells ≈ 1 MB
List size: 500 + 2,000 = 2,500 entries ≈ 20 KB

Operation analysis: Route queries ("is there a direct flight?") are common for pricing. Lists would require scanning 4 routes on average. Matrix gives O(1).

Decision: Matrix is viable (small graph) and useful for route queries. Could use list for traversals.

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
/**
 * Airline Route Planning System
 * 
 * Use case analysis:
 * - 500 airports (vertices)
 * - 2,000 routes (edges)
 * - Frequent queries: "Is there a direct flight from A to B?"
 * - Occasional: "Find all connecting flights from A"
 * 
 * Decision: Use matrix because:
 * 1. V² = 250,000 (fits easily in memory)
 * 2. Edge queries are frequent and need O(1)
 * 3. Can afford the O(V) neighbor iteration occasionally
 */
 
class AirlineNetwork {
    // Matrix stores flight times (or Infinity for no route)
    private routes: number[][];
    private airportIndex: Map<string, number>;
    
    constructor(airports: string[]) {
        const V = airports.length;
        this.routes = Array.from(
            { length: V }, 
            () => Array(V).fill(Infinity)
        );
        
        this.airportIndex = new Map();
        airports.forEach((code, i) => this.airportIndex.set(code, i));
    }
    
    addRoute(from: string, to: string, flightTime: number): void {
        const i = this.airportIndex.get(from)!;
        const j = this.airportIndex.get(to)!;
        this.routes[i][j] = flightTime;  // O(1)
    }
    
    // Primary operation: O(1) direct route check
    hasDirectFlight(from: string, to: string): boolean {
        const i = this.airportIndex.get(from)!;
        const j = this.airportIndex.get(to)!;
        return this.routes[i][j] !== Infinity;  // O(1)
    }
    
    // Can also run Floyd-Warshall for all-pairs shortest paths
    computeAllShortestPaths(): number[][] {
        // Floyd-Warshall works directly on this matrix
        // (implementation would go here)
        return this.routes;
    }
}

Example 2: Facebook Friend Recommendations

Facebook has ~3 billion users with average 500 friends each.

V = 3,000,000,000, E ≈ 750,000,000,000 (750 billion)
Matrix size: V² = 9 × 10¹⁸ cells ≈ 9 exabytes (impossible)
List size: V + 2E ≈ 1.5 trillion entries ≈ 6 TB (distributed, but feasible)

Decision: Adjacency list (distributed) is the only option. Matrix is physically impossible.

Example 3: Traveling Salesman Problem (TSP)

A delivery company optimizes routes between 100 stops.

V = 100, E = complete graph = 100×99/2 = 4,950 edges
Matrix size: 10,000 cells ≈ 80 KB
The TSP algorithm needs all pairwise distances

Decision: Matrix is perfect. Dense graph, small size, all-pairs access pattern.

Problem Size Sanity Check

Hybrid and Specialized Approaches

In complex systems, you may need the advantages of both representations. Here are sophisticated approaches:

Approach 1: Dual Representation

Maintain both an adjacency matrix and adjacency list. Use the matrix for edge queries, the list for traversals. Cost: ~2× memory, but O(1) for both key operations.

Approach 2: Cached Edge Queries

Use an adjacency list as primary representation, but cache frequently queried edges in a hash set. Adapts to access patterns at runtime.

Approach 3: Sparse Matrix Representations

For sparse graphs that need matrix operations (e.g., spectral analysis), use sparse matrix formats:

COO (Coordinate): Store (row, col, value) triples
CSR (Compressed Sparse Row): Efficient row iteration
CSC (Compressed Sparse Column): Efficient column iteration

These provide matrix semantics with O(E) space.

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
62
63
64
65
/**
 * Compressed Sparse Row (CSR) format for sparse graphs.
 * 
 * Provides matrix-like access patterns with O(V + E) space.
 * Used in scientific computing, graph ML, and sparse matrix libraries.
 */
class CSRGraph {
    // The adjacency list, but in CSR format for cache efficiency
    private values: number[];    // Edge weights (length = E)
    private colIndex: number[];  // Column indices (length = E)  
    private rowPtr: number[];    // Row start pointers (length = V + 1)
    
    constructor(vertices: number, edges: [number, number, number][]) {
        this.rowPtr = new Array(vertices + 1).fill(0);
        
        // Count edges per row
        for (const [from, _to, _weight] of edges) {
            this.rowPtr[from + 1]++;
        }
        
        // Cumulative sum to get row pointers
        for (let i = 1; i <= vertices; i++) {
            this.rowPtr[i] += this.rowPtr[i - 1];
        }
        
        // Fill in edges
        this.values = new Array(edges.length);
        this.colIndex = new Array(edges.length);
        const tempRowPtr = [...this.rowPtr];
        
        for (const [from, to, weight] of edges) {
            const idx = tempRowPtr[from]++;
            this.values[idx] = weight;
            this.colIndex[idx] = to;
        }
    }
    
    /**
     * Get neighbors of vertex v.
     * Time: O(degree(v)) — same as adjacency list
     */
    getNeighbors(v: number): { vertex: number; weight: number }[] {
        const neighbors = [];
        for (let i = this.rowPtr[v]; i < this.rowPtr[v + 1]; i++) {
            neighbors.push({
                vertex: this.colIndex[i],
                weight: this.values[i]
            });
        }
        return neighbors;
    }
    
    /**
     * Check if edge exists.
     * Time: O(degree(v)) — must scan row (unlike O(1) for dense matrix)
     * But O(log degree) with binary search if columns are sorted.
     */
    hasEdge(from: number, to: number): boolean {
        for (let i = this.rowPtr[from]; i < this.rowPtr[from + 1]; i++) {
            if (this.colIndex[i] === to) return true;
        }
        return false;
    }
}
// CSR is used by: SciPy, NumPy, graph neural network libraries (PyG, DGL)

Industry Standard Formats

Decision Checklist

Before finalizing your representation choice, run through this checklist:

Memory Check:

□ Calculated V² × bytes per cell □ Confirmed this fits in available RAM (with headroom) □ Considered cache implications for large matrices

Density Check:

□ Estimated E / V² (edge density) □ If < 5%, strongly favor lists □ If > 50%, matrix uses space well

Operation Check:

□ Identified the dominant operation(s) □ Edge existence checks → favor matrix □ Neighbor iteration → favor lists

Algorithm Check:

□ Reviewed algorithm requirements □ Matrix-based algorithms (Floyd-Warshall) → require matrix □ Traversal-based algorithms (BFS, DFS) → favor lists

Choose Matrix When...

•✓ V ≤ 5,000 (V² ≤ 25 million)
•✓ Graph is dense (E > V²/5)
•✓ Frequent edge existence queries
•✓ Running Floyd-Warshall or matrix operations
•✓ Need guaranteed O(1) worst-case lookup
•✓ Graph is static (no vertex changes)
•✓ Working with complete graphs

Choose List When...

•✓ V > 10,000
•✓ Graph is sparse (E < V × log V)
•✓ Primary operation is neighbor enumeration
•✓ Running BFS, DFS, Dijkstra
•✓ Memory is constrained
•✓ Vertices are added/removed dynamically
•✓ Working with trees or near-trees

The Default Choice

Summary: Choosing the Right Representation

We've completed our comprehensive study of adjacency matrices. Let's consolidate everything we've learned across this module:

Module Key Takeaways

•Adjacency matrices encode graphs as V×V arrays — Entry A[i][j] indicates edge from i to j; simple, elegant, powerful.
•Space cost is O(V²) — Fixed cost regardless of edge count; efficient for dense graphs, wasteful for sparse ones.
•Edge lookup is O(1) worst-case — Direct addressing guarantees constant-time edge queries, no matter what.
•Dense graphs and edge-query algorithms favor matrices — Floyd-Warshall, triangle counting, complement graphs.
•Large, sparse graphs demand alternatives — Social networks, road maps, web graphs must use adjacency lists.
•The decision is context-dependent — No single representation is 'best'; choose based on graph properties and operations.
•Hybrid approaches exist — CSR format, dual representation, and caching provide flexibility for complex systems.

What's Next:

Module Complete

4 / 4