4.20.0 — Graphs: The Pattern

Recognition cue. A grid of cells. A network of nodes and edges. Prerequisites and dependencies. "Can I get from A to B." "How many separate groups." "The fewest steps."

The first thing to realise: a grid is a graph. Each cell is a node, and its neighbours are the up to four cells beside it. You never build an adjacency list — the neighbours are computed by adding to the coordinates. Most of this chapter is grid problems, and once you see them as graphs they all become the same three algorithms.

The decision that solves almost every problem here

Ask two questions in order, and the answer falls out.

1. Am I exploring a region, or finding a shortest path?

• Region — count the islands, flood an area, mark everything reachable. Either DFS or BFS works. Use DFS: it is shorter.
• Shortest path with equal-cost steps — the fewest moves, the minimum minutes. BFS, and only BFS. DFS finds a path, not the shortest.

2. Is there an ordering or a cycle question?

• "Prerequisites", "dependencies", "build order", "is this possible" → topological sort.
• "Are these connected", "how many groups", with edges arriving one at a time → union-find.

That is the whole chapter. Three algorithms and a rule for choosing.

The three templates

# 1. DFS FLOOD FILL — regions, connected components
def dfs(r, c):
    if r < 0 or r >= rows or c < 0 or c >= cols: return
    if grid[r][c] != TARGET: return          # wrong cell, or already visited
    grid[r][c] = VISITED                     # mark BEFORE recursing
    dfs(r+1, c); dfs(r-1, c); dfs(r, c+1); dfs(r, c-1)

# 2. BFS — shortest path, level by level
queue = deque(starts)
steps = 0
while queue:
    for _ in range(len(queue)):              # one level = one step
        r, c = queue.popleft()
        for nr, nc in neighbours(r, c):
            if valid(nr, nc) and not seen[nr][nc]:
                seen[nr][nc] = True          # mark on ENQUEUE, not on dequeue
                queue.append((nr, nc))
    steps += 1

# 3. TOPOLOGICAL SORT (Kahn's) — ordering, cycle detection
indegree = [0] * n
for u, v in edges: indegree[v] += 1
queue = deque(u for u in range(n) if indegree[u] == 0)
order = []
while queue:
    u = queue.popleft()
    order.append(u)
    for v in adj[u]:
        indegree[v] -= 1
        if indegree[v] == 0: queue.append(v)
return order if len(order) == n else []      # short → there was a cycle

The three rules that prevent every common bug

Mark visited when you enqueue, not when you dequeue. Otherwise the same cell is added to the queue several times before it is ever processed, and the queue blows up. This is the most common BFS bug.

Mark before recursing in DFS, for the same reason.

Do not undo the visited mark. This is the opposite of backtracking, and mixing them up is the classic error.

• Finding a path (4.18.6 Word Search) — undo, because a cell blocked for one path must be free for another.
• Finding regions (everything here) — never undo, because a cell belongs to exactly one region and revisiting it is pure waste.

Why BFS finds shortest paths and DFS does not

BFS explores in rings: everything one step away, then everything two steps away. So the first time it reaches a node, it has arrived by the shortest route — there is no later, shorter arrival possible.

This only holds when every step costs the same. Add weights and BFS breaks, and you need Dijkstra, which is 4.21.

DFS runs to the bottom of one branch before trying another, so its first arrival can be by a long, winding route.

Multi-source BFS

Several problems start from many places at once — every rotten orange, every gate, every ocean edge. Put all the sources in the queue before the loop starts, at distance zero.

BFS then expands them all together, and each cell is reached by whichever source is nearest. No extra machinery, no running it once per source. This trick turns three of the problems below into the same six lines.

The thirteen problems

#	Problem	Tool
4.20.1	Number of Islands ★	DFS flood fill
4.20.2	Clone Graph ★	DFS + old-to-new map
4.20.3	Max Area of Island	Flood fill returning a count
4.20.4	Pacific Atlantic Water Flow ★	Reverse the flow, search from the edges
4.20.5	Surrounded Regions	Mark the survivors from the border
4.20.6	Rotting Oranges	Multi-source BFS
4.20.7	Walls and Gates	Multi-source BFS
4.20.8	Course Schedule ★	Cycle detection
4.20.9	Course Schedule II	Topological sort
4.20.10	Redundant Connection	Union-find
4.20.11	Connected Components ★	Union-find or DFS
4.20.12	Graph Valid Tree ★	Connected and n − 1 edges
4.20.13	Word Ladder ★	BFS over an implicit graph

★ marks the Blind 75 subset.

What the interviewer will push on

"Why BFS and not DFS here?" Shortest path with equal-cost edges. BFS reaches every node by its shortest route on first arrival.

"When do you mark a node visited?" On enqueue. Explain what goes wrong otherwise.

"How do you handle many starting points?" Put them all in the queue before the loop.

"How do you detect a cycle in a directed graph?" Kahn's algorithm — if the output is shorter than the node count, a cycle blocked the rest. Or DFS with three states (unvisited, in progress, done), where meeting an in-progress node means a cycle.

"Recursion depth?" DFS on a 1000×1000 grid can be a million frames deep. Use an explicit stack or BFS if that is a concern.

One thing to volunteer: say "a grid is a graph with computed neighbours" at the start. It reframes eight of these problems as the same one.

Recall

• A grid is a graph. Neighbours come from adding to coordinates; there is no adjacency list to build.
• Region → DFS or BFS. Shortest path with equal steps → BFS only. DFS finds a path, not the shortest.
• Mark visited on enqueue, not dequeue, or the queue fills with duplicates.
• Never undo the visited mark in a region search — that is backtracking, and it is a different problem shape.
• Multi-source BFS: put every start in the queue before the loop and they expand together.
• Ordering or "is it possible" → topological sort. Kahn's: repeatedly take a node with indegree 0; a short result means a cycle.
• "Connected?" with edges arriving → union-find.
• BFS's shortest-path guarantee needs equal-cost edges. Weights mean Dijkstra.

Next: 4.20.1 Number of Islands — the flood fill that eight of these problems are built from.