Topic 13 of 20
Model problems as nodes and edges; traverse with DFS and BFS, on explicit graphs and on grids.
A graph is a set of nodes connected by edges, and a surprising number of problems become easy once you recognise one. A grid is a graph where each cell connects to its neighbours. A word ladder is a graph where words differing by one letter are connected. A lock is a graph whose nodes are its combinations. Most solutions start by building an adjacency list (or treating the grid as one implicitly) and then traversing it.
DFS goes deep before backtracking and is ideal for exploring connected components, flood fills and detecting cycles. BFS explores level by level with a queue, which makes it the right tool for shortest paths in unweighted graphs. Start BFS from many sources at once (multi-source BFS) and it computes distances to the nearest source in a single pass, as in Rotting Oranges or 01 Matrix.
Always track visited nodes, and think about how each node is represented (an index, a pair of coordinates, or an entire state string). Graph problems are a major part of Google and Amazon interviews, and this topic is the foundation for Advanced Graphs and much of dynamic programming.
Counting edges on a grid without a full traversal.
Build an adjacency list and run BFS/DFS on it.
Reasoning with degrees instead of traversal.
A quick drill on reading edge lists.
The most-asked graph problem; counting connected components on a grid.
DFS that returns component size.
Components from an adjacency matrix; also a Union-Find intro.
Deep-copying a graph with an old → new map.
The canonical multi-source BFS; asked at Amazon constantly.
Distances to the nearest zero with one BFS.
8-directional BFS for shortest paths.
BFS with exit detection on the border.
Search backwards from both oceans.
Mark border-connected cells first, then flip the rest.
Cycle detection with white/grey/black DFS states.
Tracking edge direction during traversal.
Longest weighted root-to-leaf path in a hierarchy.
Answering ratio queries by path products.
BFS on a board with jumps (the Journey Map's namesake).
Shortest transformation with wildcard buckets; a Hard classic.
BFS where the state includes remaining eliminations.