Adjacency Matrix: Space-Time Tradeoffs
You'll learn when the O(V²) space cost of adjacency matrices is actually worth it.
The Core Tradeoff
An adjacency matrix always uses O(V²) space—you create a full V×V grid regardless of how many edges exist. This seems wasteful, but there's a payoff: many operations become blazingly fast.
The key insight: dense graphs (where most possible edges exist) make this tradeoff favorable. If you have a graph with V vertices and close to V² edges, you're using that matrix efficiently. Each cell holds meaningful data, not just empty space.
When Adjacency Matrices Win
Consider checking if edge (u, v) exists: with an adjacency matrix, it's O(1)—just look at matrix[u][v]. Adding or removing edges? Also O(1). Need to check all neighbors of a vertex? O(V), because you scan that vertex's row.
For sparse graphs (few edges), you're paying for V² storage but only using a fraction of it. A graph with 1000 vertices but only 2000 edges wastes most of the matrix.
The Decision Point
Use adjacency matrices when:
- Your graph is dense (edges approach V² in number)
- You need frequent edge lookups (is there an edge from A to B?)
- You're implementing algorithms that check many potential edges
- Space is acceptable given your vertex count
Think of it like buying a parking garage: if you expect it mostly full (dense), the space-per-spot makes sense. If it's usually empty (sparse), you've paid for concrete you don't need.
Key Takeaway: Adjacency matrices trade O(V²) space for O(1) edge operations—optimal for dense graphs where most connections exist and fast lookups matter more than memory efficiency.