Adjacency Matrix vs Adjacency List

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

References

• ↗ https://en.wikipedia.org/wiki/Adjacency_list

Tags

Related Terms