Graph representations
Use an adjacency list for most problems. Use a matrix when the graph is dense or edge checks dominate.
High interview relevanceRoadmap: Intermediate
| Time | Edge check: matrix O(1), list O(deg(u)) |
|---|---|
| Space | List O(V + E); matrix O(V²) |
Why it costs this much
A matrix has a cell for every pair of vertices. A list stores only the edges that exist.
Code
graph = {0: [1, 2], 1: [0, 3], 2: [0, 3], 3: [1, 2]} # list: O(V + E) space
matrix = [[0] * 4 for _ in range(4)] # matrix: O(V²) space
matrix[0][1] = matrix[1][0] = 1
matrix[0][1] # edge check: O(1)
1 in graph[0] # edge check: O(deg(0)) for a listCommon pitfalls
A matrix for 100,000 vertices needs 10 billion cells. A list answers 'is there an edge u to v' in O(deg(u)) unless neighbors are kept in a set.