What you will learn
- How to see a grid or a dependency list as a graph.
- DFS for regions, BFS for fewest steps.
- Topological sort with Kahn’s algorithm, and cycle detection for free.
Signals
- Grids where cells connect to neighbours: islands, flood fill, rotting oranges, mazes.
- “Prerequisites”, “build order”, “dependencies”, “can all tasks finish?” → topological sort.
- “Minimum number of steps/moves” with equal-cost moves → BFS.
Code
"""Graph BFS/DFS on grids and adjacency lists, plus topological sort (Kahn)."""
from collections import deque
def count_islands(grid):
rows, cols = len(grid), len(grid[0])
seen = set()
def dfs(r, c):
stack = [(r, c)] # iterative DFS avoids recursion limits on big grids
while stack:
r, c = stack.pop()
for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == "1" and (nr, nc) not in seen:
seen.add((nr, nc))
stack.append((nr, nc))
islands = 0
for r in range(rows):
for c in range(cols):
if grid[r][c] == "1" and (r, c) not in seen:
seen.add((r, c))
dfs(r, c)
islands += 1
return islands
def shortest_path_grid(grid, start, goal):
"""BFS: fewest steps in an unweighted grid ('#' is a wall)."""
rows, cols = len(grid), len(grid[0])
q, dist = deque([start]), {start: 0}
while q:
r, c = q.popleft()
if (r, c) == goal:
return dist[(r, c)]
for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] != "#" and (nr, nc) not in dist:
dist[(nr, nc)] = dist[(r, c)] + 1
q.append((nr, nc))
return -1
def course_order(n, prerequisites):
"""Kahn's algorithm. Returns an order, or [] if there's a cycle."""
graph = [[] for _ in range(n)]
indegree = [0] * n
for course, pre in prerequisites:
graph[pre].append(course)
indegree[course] += 1
q = deque(i for i in range(n) if indegree[i] == 0)
order = []
while q:
node = q.popleft()
order.append(node)
for nxt in graph[node]:
indegree[nxt] -= 1
if indegree[nxt] == 0:
q.append(nxt)
return order if len(order) == n else []
if __name__ == "__main__":
grid = ["11000",
"11000",
"00100",
"00011"]
print(count_islands(grid))
maze = ["..#.",
".##.",
"....",
"#.#."]
print(shortest_path_grid(maze, (0, 0), (0, 3)))
print(course_order(4, [[1, 0], [2, 0], [3, 1], [3, 2]]), course_order(2, [[0, 1], [1, 0]]))
Output:
3
7
[0, 1, 2, 3] []
- Islands: scan every cell; each unvisited land cell starts a DFS that marks its whole island. Mark cells as seen when you push them, so nothing is pushed twice. An explicit stack avoids Python’s recursion limit on large grids.
- Shortest path in a grid: BFS explores in rings of equal distance, so the first time it reaches the goal is the fewest steps (7 here, around the walls).
- Course order: Kahn’s algorithm repeatedly takes nodes with no remaining prerequisites. If some nodes are never taken, they sit on a cycle, so no valid order exists (the second call returns
[]).
BFS or DFS?
| Question | Use |
|---|---|
| Fewest steps, all moves cost the same | BFS |
| Visit everything / count components / detect regions | Either (DFS is often shorter) |
| Order with dependencies | Topological sort (Kahn BFS or DFS post-order) |
| Weighted edges | Dijkstra |
| Connectivity as edges arrive | Union-find |
Multi-source BFS: when the question is “distance from the nearest X” (rotting oranges, walls and gates), push every source into the queue at the start.
Practise: graph BFS/DFS, topological sort and matrix problems.
Key takeaways
- Grids are graphs with up to four neighbours per cell.
- Mark visited when pushing, not when popping, to avoid duplicates.
- BFS gives fewest steps for unweighted moves; multi-source BFS gives nearest distances.
- Kahn’s algorithm yields a topological order and detects cycles when nodes remain.
Exercises
- Rotting oranges with multi-source BFS.
- Clone a graph given as adjacency lists.
- Pacific Atlantic water flow: BFS backwards from both oceans.
Quiz
- Why does BFS find the shortest path in an unweighted graph?
- How does Kahn’s algorithm detect a cycle?
- Why mark a cell visited when pushing rather than when popping?
Show answers
- It visits nodes in order of distance; the first time a node is reached is via a path with the fewest edges.
- Nodes on a cycle never reach in-degree 0, so the output order has fewer than n nodes.
- Otherwise the same cell can be pushed many times by different neighbours before it’s processed, wasting time and memory.