The grid was a
graph all along

A graph is just things and connections: nodes (vertices) and edges. No root, no parent, no "up". Edges can be one-way (directed — Twitter follows) or two-way (undirected — Facebook friends). That's the entire definition; everything else is bookkeeping.

The bookkeeping of choice is the adjacency list: a map from each node to the list of its neighbors. Given edges as pairs, it's one line of setup — adj = defaultdict(list), then adj[u].append(v) per edge (both directions if undirected). Interviewers hand you edge lists constantly; converting to an adjacency list is the reflexive first move, like sorting was for two pointers in Chapter 5.

Two consequences of firing the boss:

• Cycles exist. A tree traversal can't revisit a node; a graph traversal absolutely can, forever. So every graph traversal carries a visited set. Non-negotiable.
• Nobody hands you the whole structure. A tree gives you the root and you can see everything. A graph may be disconnected — traversal from one node might miss whole continents. Hence the outer loop: "for every node, if not yet visited, explore from it." Each time that fires, you've found a new connected component. Hold that thought; it becomes island-counting in Section 5.

Clone Graph Medium is the purest warm-up: copy a graph you can only see one node at a time. It's a traversal plus a hash map old → copy — and the map doubles as the visited set. Chapter 4's superpower, moonlighting as graph infrastructure.

Depth-first search is the maze-runner's algorithm: at every junction, pick an unexplored corridor and commit; when you hit a dead end, walk back along your string to the last junction with an untried option. The "string" is the call stack — which is why the recursive version is three lines:

def dfs(u): visited.add(u); for v in adj[u]: if v not in visited: dfs(v)

That's Chapter 11's tree DFS with one addition — the visited check — because trees couldn't bite you and graphs can. Prefer an explicit stack? Push the start, then loop: pop, mark, push unvisited neighbors. Same exploration, your own string instead of the runtime's. On huge inputs (say a 1000×1000 grid — a million cells, per Chapter 3's constraint-sniffing) the explicit stack isn't a style choice: Python's default recursion limit dies around depth 10³, and a snake-shaped region in a million-cell grid can run orders of magnitude deeper.

DFS's personality: it's thorough, not fair. It will chase one corridor to the end of the map before glancing at the corridor next door. That makes it perfect for questions about reachability and regions — "is there a path", "mark everything connected to here", "how big is this blob" — and useless for "how far", because the order it visits things has nothing to do with distance. Cost: O(V + E) — touch every node once, slide down every edge once.

Breadth-first search is spilled water: it soaks everything one step away, then everything two steps away, then three — a wavefront expanding one ring per tick. The machinery is a queue: seed it with the start, then loop — dequeue a node, enqueue its unvisited neighbors. First-in-first-out guarantees the whole distance-1 ring is processed before anything at distance 2 gets a turn.

Here's the fact that makes BFS a pattern and not just a traversal: on an unweighted graph, the ring number where BFS first reaches a node is the shortest distance to it. Not an estimate — the answer. The water can't reach you on ring 3 if a 2-step path existed, because that path would have soaked you on ring 2. So "minimum number of moves/steps/edges" questions don't need Dijkstra, DP, or cleverness. They need a queue.

To read distances off the traversal, process the queue one floor at a time: snapshot the queue length, dequeue exactly that many, and everything you enqueued meanwhile is the next floor. Chapter 11 used this to print tree levels; here the levels mean something — floor = distance. Cost is still O(V + E), one pass, no priority queue in sight.

One discipline separates clean BFS from a subtle mess: mark visited when you enqueue, not when you dequeue. Mark-on-dequeue lets several neighbors enqueue the same node before any of them processes it — still correct, but your "queue of a frontier" bloats into a queue of duplicates, and on a fat grid that's the difference between passing and timing out.

Here's the recognition upgrade this chapter exists to install. An interview hands you a 2-D grid — land and water, walls and corridors, oranges — and the untrained eye sees a matrix: indices, nested loops, arithmetic. The trained eye sees a graph that's been pre-drawn for you: every cell is a node, and each cell has an edge to its 4 neighbors (up, down, left, right — diagonals only if the problem says so).

You never build this adjacency list; you generate neighbors on demand from a direction array — dirs = [(1,0), (-1,0), (0,1), (0,-1)] — plus a bounds check. And the grid gives you a gift no abstract graph does: the matrix itself can be the visited set. Sink an island cell by overwriting '1' → '0' and it can never be visited again — O(1) extra space, no separate structure. (If mutating input makes you itch — a reasonable itch, especially with your Scala hat on — say so out loud and offer a visited set; interviewers score the awareness.)

Once cells are nodes, everything from Sections 2–3 transfers wholesale: DFS marks regions, BFS floors measure moves, O(V + E) becomes O(m·n) — every cell touched once, four edge-checks each. Grid problems aren't a new topic. They're the same two traversals wearing a costume, which is this book's favorite sentence.

Now the payoff. Number of Islands Medium is the most-asked graph question in existence: a grid of '1' (land) and '0' (water); count the islands. Translate to graph-speak and it's Section 1's connected components verbatim: scan every cell, and each time you step on unvisited land, that's a brand-new island — count it, then flood-fill the whole blob (DFS or BFS, dealer's choice) so no cell of it ever gets counted again.

The fill is where the family lives. Make it return the number of cells it sank and you've solved Max Area of Island Medium. Make it repaint instead of sink and it's literally the paint-bucket tool (the actual Flood Fill Easy problem). The traversal never changes — only what you do per visited cell.

Paint your own archipelago below, then flood it both ways. Watch the shape of the exploration: DFS snakes down corridors and backtracks; BFS blooms outward in rings. Same cells, same island count, same O(m·n) — different personality.

Rotting Oranges Medium: a grid of fresh oranges, rotten oranges, and gaps. Every minute, rot spreads to the 4-neighbors of every rotten orange — all of them, simultaneously. How many minutes until nothing fresh remains (or -1 if some orange is unreachable)?

The word simultaneously panics people into simulation loops or one-BFS-per-source. But look at what the question actually asks: each orange rots at minute = distance to its nearest rotten source. That's a shortest-path question, so Section 3 applies — with one twist: seed the queue with every rotten orange at once, all at floor 0. Then run perfectly ordinary BFS. The wavefronts from every source expand together, each cell gets claimed by whichever source reaches it first, and the floor counter is the clock. Zero extra code beyond the seeding loop.

The endgame check is free too: after the flood, any cell still fresh was unreachable → return -1. Try it below — the preset fully rots; carve a moat of empty cells around some oranges and watch the verdict flip.

Pacific Atlantic Water Flow Medium: a grid of terrain heights; the Pacific hugs the top and left edges, the Atlantic the bottom and right; rain flows from a cell to any 4-neighbor of equal or lower height. Which cells can drain to both oceans?

The head-on attack — from every cell, search downhill and see which oceans you reach — is a full traversal per cell: O(m²n²), a number Chapter 3 taught you to flinch at. The elegant move is to reverse the question: instead of asking "which cells reach the Pacific?", ask "which cells can the Pacific reach, climbing?" Start a multi-source BFS (Section 6, already earning rent) from every coastal cell, walk edges backwards — uphill or flat — and everything you touch drains to that ocean. Two floods, one per ocean, intersect the sets. O(m·n), twice.

Surrounded Regions Medium is the same reversal wearing different clothes: "capture every region of Os not touching the border" is hard to test region-by-region, but trivial backwards — flood from the border Os, mark everything you reach as safe, capture the rest. The pattern in one sentence: when membership is defined by "can reach X", search outward from X, not from everywhere else.

Both traversals visit every reachable node in O(V + E), so for pure "explore everything" questions — counting islands, cloning, marking regions — the choice is taste (DFS is usually fewer lines). The choice stops being taste the moment the problem says a magic word:

• "Shortest", "fewest moves", "minimum minutes" → BFS. Only BFS's visit order means distance.
• "Spreads from many points at once", "nearest source" → multi-source BFS, all sources seeded at floor 0.
• "Exists a path", "connected", "count/measure regions" → DFS (or BFS — but DFS writes itself).
• "All paths", "every combination" → neither; that's exhaustive search with undo, and Chapter 18 is waiting.
• Edges with costs → Chapter 17. Connectivity under changing edges → union-find, Chapter 16.

And a scoping note, because Word Search Medium will tempt you: walking a grid to spell a word is not flood fill — the same cell may be revisited on a different path, so it's backtracking (Chapter 18), and its big sibling Word Search II bolts on Chapter 13's trie. Recognizing which side of that line a grid problem sits on is exactly the recognition skill being scored.

The pattern, as a whiteboard skeleton:

1. 1Name the graph out loud. Nodes = cells / states; edges = 4-neighbors / given pairs. Build adj from the edge list, or write dirs = [(1,0),(-1,0),(0,1),(0,-1)] for a grid.
2. 2Pick the water: distance words → BFS queue; region/reachability words → DFS stack or recursion.
3. 3Set up visited — a set, or mark the grid in place (say you're mutating input).
4. 4Seed: the start node — or every source at once for simultaneous spread, or the border/destination for reverse-flow questions.
5. 5Loop: pop a node, do the per-node work, push in-bounds unvisited neighbors — marking them visited as they're pushed.
6. 6Counting distance? Process one floor per outer tick (snapshot the queue length); floor number = answer.
7. 7Disconnected? Wrap it in "for each node, if unvisited, launch" — each launch is one component / island.
8. 8Close with the cost: O(V + E) time — O(m·n) on a grid — every node once, every edge once.

The flagship, both ways at once: the outer scan finds components, and the flood erases each one as it's counted. The Python version flood-fills with recursive DFS — the three-line maze-runner — plus a BFS variant showing that only the container changes. The Scala version goes straight to the queue (and, being Scala, feels the mutation; the comment says what to admit in the room). Either way: O(m·n) time — every cell once — and the grid itself is the visited set.