Why This Matters
Graph algorithms depend on representation. The same graph can be cheap or expensive to traverse depending on how neighbors are stored.
Decision Rule
Use an adjacency list for sparse graphs and neighbor traversal. Use an adjacency matrix when the graph is dense or the dominant operation is checking whether a specific edge exists.
Comparison Table
| Feature | Adjacency list | Adjacency matrix |
|---|---|---|
| Space | O(V + E) | O(V^2) |
Check edge u -> v | O(deg(u)) or better with sets | O(1) |
| Iterate neighbors | O(deg(u)) | O(V) |
| Sparse graph fit | excellent | wasteful |
| Dense graph fit | fine | often acceptable |
| Common algorithms | BFS, DFS, Dijkstra | Floyd-Warshall, dense graph operations |
Worked Example
A graph with one million vertices and two million edges is sparse. An adjacency matrix would need space for 10^12 possible entries, which is not practical for ordinary storage.
An adjacency list stores only existing edges, so traversal algorithms process real neighbors rather than scanning mostly empty rows.
Common Mistakes
| Mistake | Correction |
|---|---|
| Using a matrix for a huge sparse graph. | Use an adjacency list. |
| Assuming list edge checks are always constant time. | A plain list may scan neighbors; a set-backed adjacency can speed membership. |
| Ignoring algorithm expectations. | Some algorithms, such as Floyd-Warshall, are naturally matrix-shaped. |
Diagnostic Questions
| Question | Answer signal |
|---|---|
Which representation uses O(V^2) space? | Adjacency matrix. |
| Which is better for BFS on a sparse graph? | Adjacency list. |
| Which gives constant-time edge existence checks? | Adjacency matrix, or set-backed adjacency lists with different tradeoffs. |
Exercises
- Beginner: Convert a three-edge graph into an adjacency list.
- Beginner: Convert the same graph into an adjacency matrix.
- Beginner: Identify whether a graph with
EnearVis sparse or dense. - Intermediate: Implement BFS with an adjacency list.
- Intermediate: Compare memory use for
V = 10,000with sparse edges. - Challenge: Explain why Floyd-Warshall uses a distance matrix.
References
- MIT OpenCourseWare. 6.006 Introduction to Algorithms, Spring 2020: https://ocw.mit.edu/courses/6-006-introduction-to-algorithms-spring-2020/
- MIT OpenCourseWare. 6.006 Graph search materials, Spring 2020: https://ocw.mit.edu/courses/6-006-introduction-to-algorithms-spring-2020/