General
Graph representation: adjacency list vs matrix - when to use which
11 months ago
404
Quick decision guide:
Adjacency List:
- Sparse graphs (few edges)
- When you need to iterate over neighbors
- Most interview problems
- Space: O(V + E)
Adjacency Matrix:
- Dense graphs (many edges)
- When you need O(1) edge existence check
- Floyd-Warshall algorithm
- Space: O(V²)
Interview tip: Unless the problem specifically requires a matrix (like grid problems), always use an adjacency list. It's more space-efficient and interviewers expect it.
For Python: defaultdict(list) is your best friend.
graph = defaultdict(list)
for u, v in edges:
graph[u].append(v)
graphadjacency-listtutorialdsa