Interview frequency: …
Short answer
An adjacency matrix uses a two-dimensional V×V grid, which is excellent for dense graphs and checks for an edge in O(1). An adjacency list stores each vertex's neighbors in a space-efficient O(V + E) structure, ideal for sparse graphs.
Explanation
Most practical graphs, such as social and road networks, are sparse: the number of edges E is far below V^2. An adjacency matrix therefore consumes huge O(V^2) memory, mostly zeros. An adjacency list keeps only actual relationships and lets BFS and DFS iterate through neighbors in O(V + E) time.
Code example
from collections import defaultdict
# Adjacency matrix: O(V²) memory, edge check in O(1)
V = 3 # A=0, B=1, C=2
matrix = [[0] * V for _ in range(V)]
matrix[0][1] = matrix[1][0] = 1 # A - B
matrix[1][2] = matrix[2][1] = 1 # B - C
print(matrix[0][1] == 1) # is there an edge A-B?
# Adjacency list: O(V + E) memory, iterate neighbors in O(degree)
graph = defaultdict(list)
for u, v in [("A", "B"), ("B", "C")]:
graph[u].append(v)
graph[v].append(u)
print(graph["B"]) # ['A', 'C']Common mistakes
- Choosing an adjacency matrix for a graph with 1,000,000 vertices, requiring a trillion entries and causing an immediate Out Of Memory error.