Graph BFS / DFS — the shape behind dozens of interview problems.

Graph BFS / DFS in Python

from collections import deque
def shortest(grid: list[list[int]], start: tuple[int, int]) -> list[list[int]]:
    rows, cols = len(grid), len(grid[0])
    dist = [[-1] * cols for _ in range(rows)]
    q = deque([start])
    dist[start[0]][start[1]] = 0
    while q:
        r, c = q.popleft()
        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 dist[nr][nc] == -1 and grid[nr][nc] == 0:
                dist[nr][nc] = dist[r][c] + 1
                q.append((nr, nc))
    return dist

See language-specific tabs at /languages/python/patterns and the SQL variant at /languages/sql/patterns.

Related patterns

Frequently asked questions

What is the graph bfs / dfs pattern?

Graph BFS / DFS is breadth-first for shortest unweighted paths; depth-first for exhaustive traversal. Time O(V + E); space O(V).

When should I use graph bfs / dfs?

Use it when: Grid or graph traversal with connectivity. Shortest path on unweighted edges (BFS). Multi-source frontier expansion (BFS from multiple starts).

What are the most common graph bfs / dfs bugs?

Marking visited on pop instead of push → duplicate work. Using DFS on a huge grid → Python recursion-depth overflow; prefer iterative. Wrong neighbor set (8-dir vs 4-dir) for the problem's movement rules.

What problems use the graph bfs / dfs pattern?

Representative scenarios: Oil Patch Count — number of islands in a grid. Firefront Spread — BFS from all fires simultaneously. Exit-Sign Distances — shortest distance from each cell to an exit.

Is graph bfs / dfs on the Blind 75?

Yes — Graph BFS / DFS is one of the core patterns behind the Blind 75 list. See /blind-75 for the complete mapping.