Adjacency Matrix vs Adjacency List
debt(d7/e5/b5/t5)
Closest to 'only careful code review or runtime testing' (d7). The detection_hints indicate automated detection is 'no' — there are no tools listed that catch this. Identifying that someone used an adjacency matrix for a sparse graph requires manual code review or runtime profiling to notice the O(V²) memory blowup. A profiler might surface it at runtime, but it won't flag the representation choice itself, so d7 fits.
Closest to 'touches multiple files / significant refactor in one component' (e5). The quick_fix says 'use adjacency lists (array of arrays)' which sounds simple, but swapping from a matrix to a list changes the data structure's API — all code that does O(1) edge lookups via matrix[i][j] must be rewritten to iterate neighbor lists, and graph traversal algorithms may need adjustment. This typically touches multiple functions/files within the graph component, warranting e5.
Closest to 'persistent productivity tax' (b5). The graph representation choice is foundational to any graph-processing code. It applies across web and CLI contexts and shapes how every graph algorithm is written — traversal, shortest path, connectivity checks all depend on the representation. It's not quite system-defining (b7/b9) since graphs are usually one component, but it imposes a persistent tax on all graph-related work streams.
Closest to 'notable trap (a documented gotcha most devs eventually learn)' (t5). The misconception is 'adjacency matrix is always faster than adjacency list' — developers see O(1) edge lookup and assume matrix is universally superior, not realizing the O(V²) space cost makes it infeasible for sparse graphs. This is a well-documented gotcha taught in algorithms courses that most developers eventually learn, but it genuinely catches intermediate developers off guard.
Also Known As
TL;DR
Explanation
Adjacency matrix: V×V boolean array where matrix[i][j]=true means edge from i to j. O(1) edge existence check, O(V²) space — wasteful for sparse graphs (few edges). Adjacency list: array of V lists, each containing neighbours. O(V+E) space — efficient for sparse graphs. Edge existence: O(degree). Most real-world graphs are sparse (social networks, road maps, dependency trees) — adjacency lists are the default. Adjacency matrices suit: dense graphs, fast edge lookup in algorithms like Floyd-Warshall, and small graphs.
Common Misconception
Why It Matters
Common Mistakes
- Adjacency matrix for a sparse social graph — O(V²) memory makes it infeasible at scale.
- Adjacency list for a dense graph needing frequent edge queries — O(degree) lookup is slow for dense graphs.
- Not considering directed vs undirected — directed graphs need asymmetric representation.
- Forgetting to handle disconnected graphs — not all vertices have edges; the list may be empty.
Avoid When
- Avoid adjacency matrices for graphs with more than a few thousand vertices — memory blows out quadratically.
- Avoid adjacency lists when repeated random edge lookups dominate; a matrix is faster for those access patterns.
When To Use
- Use an adjacency list for sparse graphs (social networks, dependency trees) where edges ≪ V².
- Use an adjacency matrix when the graph is dense or you need O(1) edge-existence checks (e.g. game board adjacency).
- Prefer adjacency lists in PHP where memory is a concern — a list uses O(V+E) vs O(V²) for a matrix.
Code Examples
// Adjacency matrix for 1M user social graph:
$matrix = array_fill(0, 1000000, array_fill(0, 1000000, false));
// Memory: 1M * 1M * 1 byte = 1 terabyte — impossible
// Even with bits: 125 GB// Adjacency list for sparse social graph:
$graph = [];
// Average user has 200 friends:
$graph[42] = [7, 99, 156, 203]; // User 42 follows these users
// Memory: 1M users * 200 friends avg * 8 bytes = 1.6 GB — feasible
// Edge check — O(degree):
function hasEdge(array $graph, int $from, int $to): bool {
return in_array($to, $graph[$from] ?? []);
}
// For faster lookup use hash set per vertex:
$graph[42] = array_flip([7, 99, 156, 203]); // O(1) lookup