Adjacency Matrix - Learning Module

Loading content...

0/279

Edge Lookup — O(1)

The Power of Constant-Time Edge Checking

In the previous page, we analyzed the significant space cost of adjacency matrices. Now we examine what we get in return: O(1) edge existence checking.

This might seem like a minor optimization—who cares if checking an edge takes O(1) versus O(log n) or O(degree)? But in the world of graph algorithms, edge checks are often the most frequently executed operation. An algorithm that checks millions of edges will see dramatic performance differences based on this single operation's complexity.

This page explores why edge lookup in adjacency matrices is truly constant time, how this compares to alternative representations, and which algorithms and applications benefit most from this capability.

What You Will Learn

By the end of this page, you will understand the mechanics behind O(1) edge lookup, why it's genuinely constant time (not just fast on average), how this advantage manifests in specific algorithms, and when O(1) edge checking is the deciding factor in choosing adjacency matrices.

Why Edge Lookup Is O(1): Direct Address Computation

The adjacency matrix achieves constant-time edge lookup through a fundamental computer science principle: direct addressing.

The Mechanism:

When you query "Does edge (i, j) exist?", the matrix representation answers in three steps:

Compute memory address: address = base + i × V + j
Read value at that address: value = memory[address]
Compare with 'no edge' sentinel: exists = (value ≠ 0)

Each step takes constant time:

Step 1: A multiplication and two additions — O(1)
Step 2: A single memory read — O(1)
Step 3: A comparison — O(1)

Total: O(1) × 3 = O(1)

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
Direct Address Calculation:
 
For a V×V matrix stored in row-major order:
 
Physical Memory:
┌─────────────────────────────────────────────────────────────┐
│ [0,0] [0,1] [0,2] ... [0,V-1] [1,0] [1,1] ... [V-1,V-1]    │
└─────────────────────────────────────────────────────────────┘
  ↑                               ↑
  base address                    base + V (start of row 1)
 
To check if edge (i, j) exists:
 
Step 1: Calculate offset
  offset = i × V + j
 
Step 2: Calculate address  
  address = base + offset
 
Step 3: Read and compare
  value = memory[address]
  return value ≠ NO_EDGE
 
Example: V = 5, checking edge (2, 3)
  offset = 2 × 5 + 3 = 13
  address = base + 13
  → Direct jump to exact location, no searching!

Guaranteed O(1) — No Hidden Costs

Unlike hash tables (which are O(1) 'on average' but O(n) worst case), array access is O(1) in the worst case. There's no hashing function, no collision handling, no rehashing. The address calculation is pure arithmetic with no data-dependent branches.

Edge Lookup in Other Representations

To appreciate the O(1) lookup, let's compare how other graph representations answer the edge existence question:

Adjacency List:

To check if edge (i, j) exists:

Find vertex i's neighbor list: O(1)
Search for j in that list:
- If unsorted list: O(degree(i)) linear search
- If sorted list: O(log(degree(i))) binary search
- If hash set: O(1) average, O(degree(i)) worst case

For high-degree vertices (hubs in social networks), this can be expensive.

Edge List:

To check if edge (i, j) exists:

Search through all E edges: O(E)
Or, with sorted edges: O(log E)

This is prohibitive for most practical applications.

Edge Existence Check: Time Complexity Comparison
Representation	Time Complexity	Worst Case	Notes
Adjacency Matrix	O(1)	O(1)	Always constant, guaranteed
Adjacency List (array)	O(degree)	O(V)	Linear search in neighbor list
Adjacency List (sorted)	O(log degree)	O(log V)	Binary search in sorted neighbors
Adjacency List (hash set)	O(1) average	O(degree)	Hash table for each vertex's neighbors
Edge List (unsorted)	O(E)	O(V²)	Must scan all edges
Edge List (sorted)	O(log E)	O(log V²)	Binary search on sorted edges

The Key Distinction:

Adjacency matrices provide O(1) worst-case lookup. All other representations either have:

Lookup time depending on graph structure (degree, edge count)
Average-case O(1) with worst-case degradation (hash-based approaches)

When you need guaranteed constant-time edge checking—especially in performance-critical, real-time, or competitive contexts—adjacency matrices shine.

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
/**
 * Demonstrating the performance difference in edge checking.
 */
 
// Adjacency Matrix: O(1) guaranteed
class AdjMatrixGraph {
    private matrix: boolean[][];
    
    hasEdge(i: number, j: number): boolean {
        return this.matrix[i][j];  // Single array lookup
    }
}
 
// Adjacency List (array): O(degree) 
class AdjListGraph {
    private adjList: number[][];
    
    hasEdge(i: number, j: number): boolean {
        // Must search through all neighbors of i
        for (const neighbor of this.adjList[i]) {
            if (neighbor === j) return true;
        }
        return false;
        // Time: O(degree(i)) - can be O(V) for hub vertices!
    }
}
 
// Adjacency List (hash set): O(1) average, O(degree) worst
class AdjListHashGraph {
    private adjList: Set<number>[];
    
    hasEdge(i: number, j: number): boolean {
        return this.adjList[i].has(j);
        // Time: O(1) average, but hash collisions can cause O(degree)
    }
}
 
// Performance impact on repeated queries:
function checkManyEdges(graph: { hasEdge: (i: number, j: number) => boolean },
                        queries: [number, number][]) {
    let count = 0;
    for (const [i, j] of queries) {
        if (graph.hasEdge(i, j)) count++;
    }
    return count;
}
 
// For 1 million queries on a graph with high-degree hubs:
// - Matrix: ~1 million × O(1) = ~1 million operations
// - List:   ~1 million × O(average_degree) = could be 100 million+ operations

When O(1) Lookup Matters Most

Not every graph algorithm benefits equally from O(1) edge lookup. Let's identify the scenarios where this advantage is most impactful:

Scenario 1: Algorithms with Quadratic Edge Checks

Some algorithms check edges between all pairs of vertices. With V² potential pairs:

Matrix: O(V²) total edge checks
List: O(V² × average_degree) total — potentially O(V³)

Scenario 2: Dynamic Programming on Edges

DP algorithms that query edges in their recurrence (e.g., checking if vertices can be connected) benefit from fast edge checks.

Scenario 3: Random Access Patterns

When edge queries don't follow any predictable pattern (not traversing neighbors, but jumping around), matrix lookup maintains constant time while list lookup can't amortize.

Algorithms That Benefit From O(1) Edge Lookup

•Floyd-Warshall (All-Pairs Shortest Path) — O(V³) algorithm with O(V³) edge lookups; matrix lookup keeps it at O(V³) total.
•Triangle Counting — Checking if (i,j), (j,k), (i,k) all exist for all triplets; O(1) lookup is crucial.
•Graph Coloring (Backtracking) — Checking if a color is valid requires checking edges to all already-colored neighbors.
•Maximum Clique / Independent Set — Branch-and-bound algorithms check many edge existence queries.
•Matrix Exponentiation for Path Counting — Computing Aⁿ requires matrix operations where A is the adjacency matrix.
•Complement Graph Operations — Finding edges in the complement is trivial: just check if A[i][j] = 0.

The Complement Graph Advantage

An often-overlooked benefit: with an adjacency matrix, finding non-edges is just as fast as finding edges. Just check if A[i][j] = 0. With adjacency lists, finding non-edges is expensive—you must verify the edge is NOT in the neighbor list, which still requires O(degree) time.

Case Study: Floyd-Warshall and Matrix Operations

The Floyd-Warshall algorithm is a perfect example of where adjacency matrices are not just convenient but essential.

The Algorithm:

Floyd-Warshall computes shortest paths between all pairs of vertices in O(V³) time. Its core loop:

for k = 0 to V-1:
    for i = 0 to V-1:
        for j = 0 to V-1:
            dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

This accesses the distance matrix O(V³) times. The algorithm naturally operates on a V × V matrix structure.

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
/**
 * Floyd-Warshall All-Pairs Shortest Path
 * 
 * The algorithm IS the adjacency matrix — operations are performed
 * directly on the matrix structure.
 * 
 * Time: O(V³)
 * Space: O(V²) for the distance matrix
 */
function floydWarshall(adjMatrix: number[][]): number[][] {
    const V = adjMatrix.length;
    
    // Initialize distance matrix from adjacency matrix
    // dist[i][j] = weight of edge i→j, or Infinity if no edge
    const dist: number[][] = adjMatrix.map(row => [...row]);
    
    // Set diagonal to 0 (distance from vertex to itself)
    for (let i = 0; i < V; i++) {
        dist[i][i] = 0;
    }
    
    // The classic O(V³) triple loop
    for (let k = 0; k < V; k++) {
        for (let i = 0; i < V; i++) {
            for (let j = 0; j < V; j++) {
                // O(1) lookups: dist[i][k], dist[k][j], dist[i][j]
                if (dist[i][k] + dist[k][j] < dist[i][j]) {
                    dist[i][j] = dist[i][k] + dist[k][j];
                }
            }
        }
    }
    
    return dist;
}
 
// Note: Each of the V³ iterations does constant work
// because matrix access is O(1).
// 
// If we used adjacency lists, we'd need to:
// 1. Convert to matrix anyway, OR
// 2. Implement complex neighbor traversal logic
// The matrix representation IS the algorithm's natural form.

Why Matrices Are Perfect Here:

The output IS a matrix — We want all-pairs distances, which is inherently a V × V structure.
Access patterns are index-based — We access (i, k), (k, j), and (i, j) by their indices, not by neighborhood.
Every pair is considered — We're touching all V² pairs anyway, so O(V²) space is justified.
No wasted computation — Unlike traversal-based algorithms that follow edges, Floyd-Warshall explicitly considers all pairs.

Floyd-Warshall is the canonical example of an algorithm that's essentially defined in terms of matrix operations.

Matrix Exponentiation for Path Counting

Another elegant use: compute A^k (adjacency matrix raised to power k). The entry (A^k)[i][j] gives the number of paths of exactly k edges from i to j. This only works because A is already a matrix—the operation is native to the representation.

Beyond Edge Lookup: Other O(1) Operations

Edge existence checking isn't the only O(1) operation. The matrix representation enables several other constant-time capabilities:

O(1) Edge Weight Retrieval:

For weighted graphs, getting the weight of edge (i, j) is also O(1)—just read matrix[i][j]. No need to search through a list of weighted edges.

O(1) Edge Addition/Removal:

Adding or removing an edge is a single array write:

matrix[i][j] = weight;  // Add edge
matrix[i][j] = NO_EDGE; // Remove edge

With adjacency lists, these operations may require O(degree) time for deletion (finding the edge in the list) or trigger dynamic array resizing.

Common Operations: Matrix vs List Time Complexity
Operation	Adjacency Matrix	Adjacency List
Check edge exists	O(1)	O(degree) or O(log degree)
Get edge weight	O(1)	O(degree) or O(log degree)
Add edge	O(1)	O(1) amortized (append)
Remove edge	O(1)	O(degree) (find + remove)
Get all neighbors	O(V)	O(degree)
Get degree	O(V)	O(1)
Iterate all edges	O(V²)	O(V + E)

Notice the tradeoff:

Matrix excels at point queries (specific edge questions)
List excels at neighbor enumeration (what's connected to vertex i?)

Algorithms that ask "is this edge present?" favor matrices. Algorithms that ask "what are the neighbors?" favor lists. Many algorithms do both, requiring careful consideration of which operation dominates.

Edge Modification Consistency

For undirected graphs, remember to update both matrix[i][j] AND matrix[j][i] when adding/removing edges. Both operations are O(1), but forgetting one breaks the symmetry invariant. Consider wrapping in a method that enforces this.

Cache Behavior: The Hidden Performance Factor

O(1) is a theoretical guarantee, but real computers have memory hierarchies. The adjacency matrix's performance depends on cache behavior:

Row-Major Access Pattern (Cache-Friendly):

When iterating through row i (finding all neighbors of vertex i), we access consecutive memory locations. Modern CPUs fetch cache lines (typically 64 bytes), so accessing matrix[i][0] brings matrix[i][1] through matrix[i][15] into cache for free (assuming 4-byte integers).

Random Access Pattern (Less Cache-Friendly):

When making random edge queries (e.g., check (7, 42), then (1000, 5), then (3, 99)), each query likely causes a cache miss. The matrix is too large to fit in cache, and queries don't exhibit locality.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
Cache Behavior Visualization:
 
Matrix Layout in Memory (Row-Major):
┌─────────────────────────────────────────────────────────────┐
│ Row 0 │ Row 1 │ Row 2 │ ... │ Row V-1                       │
└─────────────────────────────────────────────────────────────┘
 
Scenario A: Iterating neighbors of vertex 5
Access pattern: matrix[5][0], matrix[5][1], matrix[5][2], ...
→ Sequential memory access → Cache-friendly → Fast
 
Scenario B: Random edge queries  
Access pattern: matrix[42][100], matrix[7][999], matrix[500][3], ...
→ Each access may hit different cache lines → Cache misses → Slower
 
Cache Line (64 bytes = 16 integers):
┌────┬────┬────┬────┬────┬────┬────┬────┬────┬────┬────┬────┬────┬────┬────┬────┐
│ 0  │ 1  │ 2  │ 3  │ 4  │ 5  │ 6  │ 7  │ 8  │ 9  │ 10 │ 11 │ 12 │ 13 │ 14 │ 15 │
└────┴────┴────┴────┴────┴────┴────┴────┴────┴────┴────┴────┴────┴────┴────┴────┘
  ↑
  Accessing one brings all 16 into L1 cache

Practical Implications:

Floyd-Warshall has excellent cache behavior—it scans rows sequentially.
Random edge queries (e.g., checking if a specific edge exists during many independent queries) have poor locality but still benefit from O(1) vs O(degree).
Column access (finding all vertices that connect TO a given vertex) has poor cache behavior—each access is V elements apart. Consider storing the transpose matrix if this pattern is common.
For very large matrices, even with O(1) lookup, cache miss penalties can dominate. A cache miss to main memory takes ~100-200 CPU cycles, compared to ~4 cycles for an L1 cache hit.

When Cache Misses Dominate

For matrices too large to fit in L3 cache (typically 8-64 MB), random edge queries may take 100+ nanoseconds each. This is still O(1), but the constant factor is high. For such large graphs, even O(log degree) with good locality might outperform O(1) with poor locality.

Practical Trade-off Analysis

Let's synthesize when the O(1) edge lookup justifies the O(V²) space cost:

Strong Case for Adjacency Matrix:

✓ Graph is small enough to fit comfortably in memory ✓ Graph is dense (many edges) ✓ Algorithm requires many edge existence checks ✓ Algorithm is inherently matrix-based (Floyd-Warshall, matrix exponentiation) ✓ Need O(1) worst-case guarantee (real-time systems) ✓ Will modify edges frequently (add/remove in O(1))

Weak Case for Adjacency Matrix:

✗ Graph is sparse (most cells would be zero) ✗ Primary operations are neighbor enumeration (traversals) ✗ Graph is too large for V² space ✗ Algorithm already runs in O(V + E) and wouldn't benefit from faster edge lookup

Use Matrix When...

•V ≤ 10,000 and you have sufficient RAM
•Edge density > 10% (E > V²/10)
•Running all-pairs algorithms
•Real-time edge query requirements
•Implementing complement graph operations
•Matrix algebra on graphs is needed

Avoid Matrix When...

•V > 50,000 (memory becomes prohibitive)
•Graph is tree-like or very sparse
•Primary operation is BFS/DFS traversal
•Memory is constrained (embedded systems)
•Graph changes structure frequently (vertices added/removed)
•Social network scale (millions of vertices)

The Hybrid Approach

In practice, some systems maintain both representations: an adjacency list for traversals and a hash-set-based structure for edge queries. This uses more memory but provides near-optimal performance for both operation types. Consider this when both patterns are critical.

Summary: The O(1) Edge Lookup Advantage

We've thoroughly explored the O(1) edge lookup capability that adjacency matrices provide. Let's consolidate the key insights:

Key Takeaways

•O(1) lookup comes from direct addressing — The address of A[i][j] is computed with simple arithmetic, then read in one memory access.
•It's worst-case O(1), not just average — Unlike hash tables, there's no degradation from collisions or bad inputs.
•Adjacency lists require O(degree) for edge lookup — This can be O(V) for hub vertices in scale-free networks.
•Matrix operations benefit most — Floyd-Warshall, matrix exponentiation, and triangle counting all rely on fast edge checks.
•Other O(1) operations — Edge addition, removal, and weight retrieval are also constant time.
•Cache behavior matters — Sequential row access is cache-friendly; random access incurs cache misses.
•Trade-offs are context-dependent — Dense graphs and edge-query-heavy algorithms favor matrices; sparse graphs and traversals favor lists.

What's Next:

We've established both the cost (O(V²) space) and the benefit (O(1) lookup) of adjacency matrices. The final page synthesizes these into practical guidance: when are adjacency matrices the right choice? We'll provide decision frameworks and real-world examples.

O(1) Analysis Complete

You now understand why adjacency matrix edge lookup is truly O(1), how this compares to alternatives, and which algorithms benefit most. This knowledge prepares you to make informed decisions about graph representation. Next: synthesizing everything into practical guidance.

Edge Lookup — O(1)

The Power of Constant-Time Edge Checking

In the previous page, we analyzed the significant space cost of adjacency matrices. Now we examine what we get in return: O(1) edge existence checking.

What You Will Learn

Why Edge Lookup Is O(1): Direct Address Computation

The adjacency matrix achieves constant-time edge lookup through a fundamental computer science principle: direct addressing.

The Mechanism:

When you query "Does edge (i, j) exist?", the matrix representation answers in three steps:

Compute memory address: address = base + i × V + j
Read value at that address: value = memory[address]
Compare with 'no edge' sentinel: exists = (value ≠ 0)

Each step takes constant time:

Step 1: A multiplication and two additions — O(1)
Step 2: A single memory read — O(1)
Step 3: A comparison — O(1)

Total: O(1) × 3 = O(1)

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
Direct Address Calculation:
 
For a V×V matrix stored in row-major order:
 
Physical Memory:
┌─────────────────────────────────────────────────────────────┐
│ [0,0] [0,1] [0,2] ... [0,V-1] [1,0] [1,1] ... [V-1,V-1]    │
└─────────────────────────────────────────────────────────────┘
  ↑                               ↑
  base address                    base + V (start of row 1)
 
To check if edge (i, j) exists:
 
Step 1: Calculate offset
  offset = i × V + j
 
Step 2: Calculate address  
  address = base + offset
 
Step 3: Read and compare
  value = memory[address]
  return value ≠ NO_EDGE
 
Example: V = 5, checking edge (2, 3)
  offset = 2 × 5 + 3 = 13
  address = base + 13
  → Direct jump to exact location, no searching!

Guaranteed O(1) — No Hidden Costs

Edge Lookup in Other Representations

To appreciate the O(1) lookup, let's compare how other graph representations answer the edge existence question:

Adjacency List:

To check if edge (i, j) exists:

Find vertex i's neighbor list: O(1)
Search for j in that list:
- If unsorted list: O(degree(i)) linear search
- If sorted list: O(log(degree(i))) binary search
- If hash set: O(1) average, O(degree(i)) worst case

For high-degree vertices (hubs in social networks), this can be expensive.

Edge List:

To check if edge (i, j) exists:

Search through all E edges: O(E)
Or, with sorted edges: O(log E)

This is prohibitive for most practical applications.

Edge Existence Check: Time Complexity Comparison
Representation	Time Complexity	Worst Case	Notes
Adjacency Matrix	O(1)	O(1)	Always constant, guaranteed
Adjacency List (array)	O(degree)	O(V)	Linear search in neighbor list
Adjacency List (sorted)	O(log degree)	O(log V)	Binary search in sorted neighbors
Adjacency List (hash set)	O(1) average	O(degree)	Hash table for each vertex's neighbors
Edge List (unsorted)	O(E)	O(V²)	Must scan all edges
Edge List (sorted)	O(log E)	O(log V²)	Binary search on sorted edges

The Key Distinction:

Adjacency matrices provide O(1) worst-case lookup. All other representations either have:

Lookup time depending on graph structure (degree, edge count)
Average-case O(1) with worst-case degradation (hash-based approaches)

When you need guaranteed constant-time edge checking—especially in performance-critical, real-time, or competitive contexts—adjacency matrices shine.

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
/**
 * Demonstrating the performance difference in edge checking.
 */
 
// Adjacency Matrix: O(1) guaranteed
class AdjMatrixGraph {
    private matrix: boolean[][];
    
    hasEdge(i: number, j: number): boolean {
        return this.matrix[i][j];  // Single array lookup
    }
}
 
// Adjacency List (array): O(degree) 
class AdjListGraph {
    private adjList: number[][];
    
    hasEdge(i: number, j: number): boolean {
        // Must search through all neighbors of i
        for (const neighbor of this.adjList[i]) {
            if (neighbor === j) return true;
        }
        return false;
        // Time: O(degree(i)) - can be O(V) for hub vertices!
    }
}
 
// Adjacency List (hash set): O(1) average, O(degree) worst
class AdjListHashGraph {
    private adjList: Set<number>[];
    
    hasEdge(i: number, j: number): boolean {
        return this.adjList[i].has(j);
        // Time: O(1) average, but hash collisions can cause O(degree)
    }
}
 
// Performance impact on repeated queries:
function checkManyEdges(graph: { hasEdge: (i: number, j: number) => boolean },
                        queries: [number, number][]) {
    let count = 0;
    for (const [i, j] of queries) {
        if (graph.hasEdge(i, j)) count++;
    }
    return count;
}
 
// For 1 million queries on a graph with high-degree hubs:
// - Matrix: ~1 million × O(1) = ~1 million operations
// - List:   ~1 million × O(average_degree) = could be 100 million+ operations

When O(1) Lookup Matters Most

Not every graph algorithm benefits equally from O(1) edge lookup. Let's identify the scenarios where this advantage is most impactful:

Scenario 1: Algorithms with Quadratic Edge Checks

Some algorithms check edges between all pairs of vertices. With V² potential pairs:

Matrix: O(V²) total edge checks
List: O(V² × average_degree) total — potentially O(V³)

Scenario 2: Dynamic Programming on Edges

DP algorithms that query edges in their recurrence (e.g., checking if vertices can be connected) benefit from fast edge checks.

Scenario 3: Random Access Patterns

When edge queries don't follow any predictable pattern (not traversing neighbors, but jumping around), matrix lookup maintains constant time while list lookup can't amortize.

Algorithms That Benefit From O(1) Edge Lookup

•Floyd-Warshall (All-Pairs Shortest Path) — O(V³) algorithm with O(V³) edge lookups; matrix lookup keeps it at O(V³) total.
•Triangle Counting — Checking if (i,j), (j,k), (i,k) all exist for all triplets; O(1) lookup is crucial.
•Graph Coloring (Backtracking) — Checking if a color is valid requires checking edges to all already-colored neighbors.
•Maximum Clique / Independent Set — Branch-and-bound algorithms check many edge existence queries.
•Matrix Exponentiation for Path Counting — Computing Aⁿ requires matrix operations where A is the adjacency matrix.
•Complement Graph Operations — Finding edges in the complement is trivial: just check if A[i][j] = 0.

The Complement Graph Advantage

Case Study: Floyd-Warshall and Matrix Operations

The Floyd-Warshall algorithm is a perfect example of where adjacency matrices are not just convenient but essential.

The Algorithm:

Floyd-Warshall computes shortest paths between all pairs of vertices in O(V³) time. Its core loop:

for k = 0 to V-1:
    for i = 0 to V-1:
        for j = 0 to V-1:
            dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

This accesses the distance matrix O(V³) times. The algorithm naturally operates on a V × V matrix structure.

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
/**
 * Floyd-Warshall All-Pairs Shortest Path
 * 
 * The algorithm IS the adjacency matrix — operations are performed
 * directly on the matrix structure.
 * 
 * Time: O(V³)
 * Space: O(V²) for the distance matrix
 */
function floydWarshall(adjMatrix: number[][]): number[][] {
    const V = adjMatrix.length;
    
    // Initialize distance matrix from adjacency matrix
    // dist[i][j] = weight of edge i→j, or Infinity if no edge
    const dist: number[][] = adjMatrix.map(row => [...row]);
    
    // Set diagonal to 0 (distance from vertex to itself)
    for (let i = 0; i < V; i++) {
        dist[i][i] = 0;
    }
    
    // The classic O(V³) triple loop
    for (let k = 0; k < V; k++) {
        for (let i = 0; i < V; i++) {
            for (let j = 0; j < V; j++) {
                // O(1) lookups: dist[i][k], dist[k][j], dist[i][j]
                if (dist[i][k] + dist[k][j] < dist[i][j]) {
                    dist[i][j] = dist[i][k] + dist[k][j];
                }
            }
        }
    }
    
    return dist;
}
 
// Note: Each of the V³ iterations does constant work
// because matrix access is O(1).
// 
// If we used adjacency lists, we'd need to:
// 1. Convert to matrix anyway, OR
// 2. Implement complex neighbor traversal logic
// The matrix representation IS the algorithm's natural form.

Why Matrices Are Perfect Here:

The output IS a matrix — We want all-pairs distances, which is inherently a V × V structure.
Access patterns are index-based — We access (i, k), (k, j), and (i, j) by their indices, not by neighborhood.
Every pair is considered — We're touching all V² pairs anyway, so O(V²) space is justified.
No wasted computation — Unlike traversal-based algorithms that follow edges, Floyd-Warshall explicitly considers all pairs.

Floyd-Warshall is the canonical example of an algorithm that's essentially defined in terms of matrix operations.

Matrix Exponentiation for Path Counting

Beyond Edge Lookup: Other O(1) Operations

Edge existence checking isn't the only O(1) operation. The matrix representation enables several other constant-time capabilities:

O(1) Edge Weight Retrieval:

For weighted graphs, getting the weight of edge (i, j) is also O(1)—just read matrix[i][j]. No need to search through a list of weighted edges.

O(1) Edge Addition/Removal:

Adding or removing an edge is a single array write:

matrix[i][j] = weight;  // Add edge
matrix[i][j] = NO_EDGE; // Remove edge

With adjacency lists, these operations may require O(degree) time for deletion (finding the edge in the list) or trigger dynamic array resizing.

Common Operations: Matrix vs List Time Complexity
Operation	Adjacency Matrix	Adjacency List
Check edge exists	O(1)	O(degree) or O(log degree)
Get edge weight	O(1)	O(degree) or O(log degree)
Add edge	O(1)	O(1) amortized (append)
Remove edge	O(1)	O(degree) (find + remove)
Get all neighbors	O(V)	O(degree)
Get degree	O(V)	O(1)
Iterate all edges	O(V²)	O(V + E)

Notice the tradeoff:

Matrix excels at point queries (specific edge questions)
List excels at neighbor enumeration (what's connected to vertex i?)

Edge Modification Consistency

Cache Behavior: The Hidden Performance Factor

O(1) is a theoretical guarantee, but real computers have memory hierarchies. The adjacency matrix's performance depends on cache behavior:

Row-Major Access Pattern (Cache-Friendly):

Random Access Pattern (Less Cache-Friendly):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
Cache Behavior Visualization:
 
Matrix Layout in Memory (Row-Major):
┌─────────────────────────────────────────────────────────────┐
│ Row 0 │ Row 1 │ Row 2 │ ... │ Row V-1                       │
└─────────────────────────────────────────────────────────────┘
 
Scenario A: Iterating neighbors of vertex 5
Access pattern: matrix[5][0], matrix[5][1], matrix[5][2], ...
→ Sequential memory access → Cache-friendly → Fast
 
Scenario B: Random edge queries  
Access pattern: matrix[42][100], matrix[7][999], matrix[500][3], ...
→ Each access may hit different cache lines → Cache misses → Slower
 
Cache Line (64 bytes = 16 integers):
┌────┬────┬────┬────┬────┬────┬────┬────┬────┬────┬────┬────┬────┬────┬────┬────┐
│ 0  │ 1  │ 2  │ 3  │ 4  │ 5  │ 6  │ 7  │ 8  │ 9  │ 10 │ 11 │ 12 │ 13 │ 14 │ 15 │
└────┴────┴────┴────┴────┴────┴────┴────┴────┴────┴────┴────┴────┴────┴────┴────┘
  ↑
  Accessing one brings all 16 into L1 cache

Practical Implications:

Floyd-Warshall has excellent cache behavior—it scans rows sequentially.
Random edge queries (e.g., checking if a specific edge exists during many independent queries) have poor locality but still benefit from O(1) vs O(degree).
Column access (finding all vertices that connect TO a given vertex) has poor cache behavior—each access is V elements apart. Consider storing the transpose matrix if this pattern is common.
For very large matrices, even with O(1) lookup, cache miss penalties can dominate. A cache miss to main memory takes ~100-200 CPU cycles, compared to ~4 cycles for an L1 cache hit.

When Cache Misses Dominate

Practical Trade-off Analysis

Let's synthesize when the O(1) edge lookup justifies the O(V²) space cost:

Strong Case for Adjacency Matrix:

Weak Case for Adjacency Matrix:

Use Matrix When...

•V ≤ 10,000 and you have sufficient RAM
•Edge density > 10% (E > V²/10)
•Running all-pairs algorithms
•Real-time edge query requirements
•Implementing complement graph operations
•Matrix algebra on graphs is needed

Avoid Matrix When...

•V > 50,000 (memory becomes prohibitive)
•Graph is tree-like or very sparse
•Primary operation is BFS/DFS traversal
•Memory is constrained (embedded systems)
•Graph changes structure frequently (vertices added/removed)
•Social network scale (millions of vertices)

The Hybrid Approach

Summary: The O(1) Edge Lookup Advantage

We've thoroughly explored the O(1) edge lookup capability that adjacency matrices provide. Let's consolidate the key insights:

Key Takeaways

•O(1) lookup comes from direct addressing — The address of A[i][j] is computed with simple arithmetic, then read in one memory access.
•It's worst-case O(1), not just average — Unlike hash tables, there's no degradation from collisions or bad inputs.
•Adjacency lists require O(degree) for edge lookup — This can be O(V) for hub vertices in scale-free networks.
•Matrix operations benefit most — Floyd-Warshall, matrix exponentiation, and triangle counting all rely on fast edge checks.
•Other O(1) operations — Edge addition, removal, and weight retrieval are also constant time.
•Cache behavior matters — Sequential row access is cache-friendly; random access incurs cache misses.
•Trade-offs are context-dependent — Dense graphs and edge-query-heavy algorithms favor matrices; sparse graphs and traversals favor lists.

What's Next:

O(1) Analysis Complete