CONCEPT · Specialist
Graph representation
also adjacency list · implicit graph
Nodes and edges. Store adjacency lists for sparse graphs; treat grids and 'next state' problems as implicit graphs you never fully materialize.
Intuition
If you can name neighbors of a state, you have a graph. BFS/DFS do not care whether the edge list lives in memory.
When to reach for it
- Road networks, friendships, dependencies
- Mazes and grids
- State-space search (digit DP cousins, knight moves)
Usual pits
- Adjacency matrix at n = 1e5 (memory)
- Forgetting bidirectional edges on undirected input
- 1-based node ids into 0-based vectors