Graph traversal — BFS and DFS

BFS for fewest steps, DFS for reachability and structure.

The tell: Grids, islands, mazes, dependencies, connected components, or 'shortest path' with unit edges.

Reach for it when

Shortest path on an unweighted graph or grid — BFS
Counting islands / flood fill — DFS or BFS
Cycle detection in a directed graph — DFS with three colours
Bipartite check — BFS colouring

Reference implementation

bfs_shortest — grid, 4-directional

from collections import deque

def bfs_shortest(grid: list[list[int]]) -> int:
    """Fewest steps from (0,0) to the bottom-right through 0 cells; -1 if blocked."""
    if not grid or grid[0][0] == 1:
        return -1
    rows, cols = len(grid), len(grid[0])
    queue = deque([(0, 0, 1)])
    seen = {(0, 0)}                      # mark on push, not on pop
    while queue:
        r, c, dist = queue.popleft()
        if (r, c) == (rows - 1, cols - 1):
            return dist
        for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            nr, nc = r + dr, c + dc
            if 0 <= nr < rows and 0 <= nc < cols \
                    and grid[nr][nc] == 0 and (nr, nc) not in seen:
                seen.add((nr, nc))
                queue.append((nr, nc, dist + 1))
    return -1

Complexity: O(V + E). BFS uses O(V) queue space; recursive DFS uses O(V) stack.

What goes wrong

Marking visited on pop instead of on push — the same cell is queued many times and BFS degrades badly.
Using a list with `pop(0)` instead of `collections.deque`, turning O(1) into O(n).
Recursive DFS on a large grid hitting Python's ~1000 default recursion limit.

Practise on

Number of Islands
Rotting Oranges
Word Ladder
Course Schedule
Shortest Path in Binary Matrix

Test yourself on DSA Next pattern: Topological sort →