Pattern 4: A grid is a graph and multi-source BFS
You already treated grids as graphs in the Matrix section. Here we close that idea and add a powerful tool: multi-source BFS, which starts from several points at the same time — perfect for "how long until everything is reached?".
Try it first: Rotting Oranges
Before reading the theory, try to solve it. You can start with brute force, you can fail — the point is to feel the problem. The theory comes right below.
In a grid, 0 = empty, 1 = fresh orange, 2 = rotten orange. Each minute, every rotten orange rots the adjacent fresh ones (horizontal/vertical). Return the number of minutes until no fresh orange remains, or -1 if it is impossible.
Example: [[2,1,1],[1,1,0],[0,1,1]] → 4.
Tried it? If you ran a separate BFS from each rotten orange, it works but it is confusing and slow. The theory below shows how to drop all the sources into the queue at once.
The theory: grid as a graph (review) + several sources
In a grid, each cell is a node and the neighboring cells (up/down/left/right) are connected by edges. That is why DFS/BFS on a grid are the same graph algorithms — with the "adjacency list" implicit in the 4 neighbors.
The novelty is multi-source BFS. In ordinary BFS, the queue starts with one origin. In multi-source, you place all the origins in the queue at time 0 and let the waves expand simultaneously. Each cell is reached by the nearest source, in the correct layer (= time/distance):
queue ← ALL the sources (time 0); mark them
while the queue is not empty:
(cell, time) = dequeue
for each valid neighbor not yet reached:
mark, enqueue with time + 1
the largest time reached is the answer
In Rotting Oranges, the sources are all the initial rotten oranges; at each minute (BFS layer), they rot the fresh neighbors. The number of layers is the total time. And if, at the end, a fresh orange still remains (a region that no wave reached), the answer is -1.
Why is multi-source better than running a BFS from each source?
Running a separate BFS from each of the k sources would cost O(k · (V+E)).
Multi-source solves everything in a single BFS, O(V+E), because the waves
advance together and each cell is processed once — reached automatically by the
nearest source. For the grid, O(m·n).
Another example: Pacific Atlantic Water Flow
"From which cells does water flow both to the Pacific Ocean (top/left edges) and to the Atlantic (bottom/right edges)?" The trick is the same inversion as in the Matrix section: instead of testing each cell, run searches from the edges (the sources!) climbing toward cells of greater or equal height. The cells reachable by both oceans are the intersection. It is multi-source search again — starting from a whole set of edges.
The transferable lesson: when the problem has many starting points (all the rotten ones, all the edges, all the exit doors), do not run a search for each — drop all of them into the queue and let the waves meet.
🧠 Review quiz
0/41. Why can a grid be treated as a graph?
2. What characterizes a MULTI-SOURCE BFS?
3. In Rotting Oranges, how do you know the answer is -1?
4. Why is multi-source BFS better than running a separate BFS from each source?
Summary
- A grid is a graph: cells = nodes, neighbors = edges; DFS/BFS apply directly.
- Multi-source BFS: drop all the sources into the queue at time 0; the waves expand together, each cell reached by the nearest source.
- Rotting Oranges (time until everything rots; -1 if a fresh one remains), Pacific Atlantic (searches from the edges) — both multi-source. O(m·n).
Last stop: the synthesis of the Graph section and the quiz before the exam.