Topic 13 of 20
Graphs (BFS, DFS, Grid)
Model problems as nodes and edges; traverse with DFS and BFS, on explicit graphs and on grids.
The concept
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.
Patterns you will learn
Problems, in order
- 1
- 2Island PerimeterEasy
Counting edges on a grid without a full traversal.
Grid IterationReported at: MetaGoogleAmazon - 3
Build an adjacency list and run BFS/DFS on it.
Connected ComponentsReported at: AmazonGoogle - 4
Reasoning with degrees instead of traversal.
In/Out DegreeReported at: GoogleAmazonApple+1 - 5
A quick drill on reading edge lists.
Degree ReasoningReported at: Microsoft - 6Number of IslandsMedium
The most-asked graph problem; counting connected components on a grid.
Grid DFS / Flood FillReported at: AmazonMicrosoftMeta+16 - 7Max Area of IslandMedium
DFS that returns component size.
Grid DFS / Flood FillReported at: AmazonMetaMicrosoft+4 - 8Number of ProvincesMedium
Components from an adjacency matrix; also a Union-Find intro.
- 9Clone GraphMedium
Deep-copying a graph with an old → new map.
DFS/BFS + Hash MapReported at: MetaAmazonGoogle+2 - 10
- 11
- 12Rotting OrangesMedium
The canonical multi-source BFS; asked at Amazon constantly.
Multi-source BFSReported at: AmazonMicrosoftVMware+1 - 1301 MatrixMedium
Distances to the nearest zero with one BFS.
Multi-source BFSReported at: GoogleAmazonMeta+1 - 14
- 15
8-directional BFS for shortest paths.
BFS Shortest Path (Unweighted)Reported at: MetaAmazonMicrosoft+3 - 16
BFS with exit detection on the border.
BFS Shortest Path (Unweighted)Reported at: Amazon - 17
Search backwards from both oceans.
Reverse Multi-source DFSReported at: GoogleAmazonUber+1 - 18Surrounded RegionsMedium
Mark border-connected cells first, then flip the rest.
Border DFSReported at: GoogleBloombergUber+1 - 19
- 20
- 21
- 22
- 23
- 24
Cycle detection with white/grey/black DFS states.
- 25
Tracking edge direction during traversal.
DFS with Edge DirectionReported at: Amazon - 26
Longest weighted root-to-leaf path in a hierarchy.
Tree DFS / BFSReported at: GoogleAmazon - 27Evaluate DivisionMedium
Answering ratio queries by path products.
Weighted Graph DFSReported at: AmazonGoogleMeta+5 - 28Snakes and LaddersMedium
BFS on a board with jumps (the Journey Map's namesake).
- 29
- 30
- 31Word LadderHard
Shortest transformation with wildcard buckets; a Hard classic.
Implicit Graph / State-space BFSReported at: AmazonMetaMicrosoft+4 - 32
BFS where the state includes remaining eliminations.
- 33
- 34
- 35