Graphs: BFS, DFS and Grids

A graph is a set of nodes connected by edges, and a surprising number of problems are graphs in disguise: a grid of cells, a set of dependencies, a word list where words differing by one letter are neighbours, a state space in a puzzle. Two traversals, depth-first search (DFS) and breadth-first search (BFS), solve most of them. The hard part is usually not the traversal, but modelling the problem as a graph and avoiding visiting nodes twice.

1. When this pattern applies

• Items are connected by relationships: friends, roads, links, dependencies, moves.
• You need to explore everything reachable from a start, count connected regions, or find a path.
• You need the shortest path in an unweighted graph (number of steps). That is BFS.
• The input is a grid and you move up, down, left and right.
• You search a state space (puzzles, word transformations) where each state has a few neighbours.

2. Representing a graph

Adjacency list (the default): a dictionary or list mapping each node to its neighbours. Space $O(V+E)$, and iterating a node's neighbours is proportional to its degree.

from collections import defaultdict

def build_graph(edges, directed=False):
    graph = defaultdict(list)
    for a, b in edges:
        graph[a].append(b)
        if not directed:
            graph[b].append(a)
    return graph

g = build_graph([(0, 1), (0, 2), (1, 3), (4, 5)])
assert sorted(g[0]) == [1, 2] and sorted(g[3]) == [1]

Adjacency matrix: matrix[i][j] is 1 if an edge exists. Space $O(V^2)$, good for dense graphs and constant-time edge checks. Edge list is the raw input form. State which representation you choose and why.

Terms to use precisely: directed versus undirected, weighted, connected component, cycle, DAG (directed acyclic graph), degree, $V$ for the number of nodes and $E$ for edges. Traversal cost is $O(V+E)$.

3. Depth-first search

DFS goes as deep as possible along one path before backtracking. Implement it recursively, or iteratively with a stack. You must mark nodes visited to avoid infinite loops on cycles.

def dfs_recursive(graph, start):
    seen, order = set(), []
    def visit(node):
        seen.add(node)
        order.append(node)
        for nxt in graph[node]:
            if nxt not in seen:
                visit(nxt)
    visit(start)
    return order

def dfs_iterative(graph, start):
    seen, order, stack = set(), [], [start]
    while stack:
        node = stack.pop()
        if node in seen:
            continue
        seen.add(node)
        order.append(node)
        for nxt in graph[node]:
            if nxt not in seen:
                stack.append(nxt)
    return order

g = build_graph([(0, 1), (0, 2), (1, 3), (2, 3), (4, 5)])
assert set(dfs_recursive(g, 0)) == {0, 1, 2, 3}
assert set(dfs_iterative(g, 0)) == {0, 1, 2, 3}

Count connected components: start a DFS from every unvisited node and count the starts.

def count_components(n, edges):
    graph = build_graph(edges)
    seen = set()
    def visit(node):
        seen.add(node)
        for nxt in graph[node]:
            if nxt not in seen:
                visit(nxt)
    count = 0
    for node in range(n):
        if node not in seen:
            visit(node)
            count += 1
    return count

assert count_components(5, [(0, 1), (1, 2), (3, 4)]) == 2
assert count_components(4, []) == 4

Time $O(V+E)$, space $O(V)$ for the visited set and the recursion stack. Python's default recursion limit (about 1,000) can be exceeded on a long path graph, so for large inputs use the iterative version, or raise the limit.

4. Breadth-first search

BFS explores in layers: all nodes at distance 1, then distance 2, and so on. Use a queue. Because the first time BFS reaches a node is along a shortest path (in number of edges), BFS gives shortest paths in unweighted graphs.

from collections import deque

def bfs_distances(graph, start):
    dist = {start: 0}
    queue = deque([start])
    while queue:
        node = queue.popleft()
        for nxt in graph[node]:
            if nxt not in dist:                     # first visit = shortest
                dist[nxt] = dist[node] + 1
                queue.append(nxt)
    return dist

g = build_graph([(0, 1), (0, 2), (1, 3), (2, 3), (3, 4)])
assert bfs_distances(g, 0) == {0: 0, 1: 1, 2: 1, 3: 2, 4: 3}

Mark nodes visited when you enqueue them, not when you dequeue them, or the same node can be queued many times and the algorithm slows down or loops.

DFS or BFS? Use BFS when you need the shortest path or the fewest steps, or level order. Use DFS for exhaustive exploration, connectivity, cycle detection, backtracking and anything naturally recursive. Both are $O(V+E)$.

5. Grids as graphs

In a grid, each cell is a node, and its neighbours are the adjacent cells (4 or 8 directions). You usually do not build an adjacency list. You compute neighbours on the fly with direction offsets and bounds checks.

DIRS = [(1, 0), (-1, 0), (0, 1), (0, -1)]

def neighbours(r, c, rows, cols):
    for dr, dc in DIRS:
        nr, nc = r + dr, c + dc
        if 0 <= nr < rows and 0 <= nc < cols:
            yield nr, nc

assert sorted(neighbours(0, 0, 3, 3)) == [(0, 1), (1, 0)]

Number of islands. Count connected groups of 1 cells. For each unvisited land cell, flood-fill its island and count it. Modifying the grid in place (changing visited 1 to 0) avoids a separate visited set.

def num_islands(grid):
    if not grid:
        return 0
    rows, cols = len(grid), len(grid[0])
    def sink(r, c):
        stack = [(r, c)]
        grid[r][c] = "0"
        while stack:
            cr, cc = stack.pop()
            for nr, nc in neighbours(cr, cc, rows, cols):
                if grid[nr][nc] == "1":
                    grid[nr][nc] = "0"                 # mark visited when pushing
                    stack.append((nr, nc))
    count = 0
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == "1":
                sink(r, c)
                count += 1
    return count

grid = [list("11000"), list("11000"), list("00100"), list("00011")]
assert num_islands(grid) == 3
assert num_islands([]) == 0

Time $O(R\times C)$, since each cell is visited a constant number of times. Space $O(R\times C)$ worst case for the stack. If the caller does not want the input modified, use a visited set, or restore the grid.

Maximum area of an island returns the size of the largest flood fill.

def max_area_of_island(grid):
    rows, cols = len(grid), len(grid[0])
    best = 0
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == 1:
                area, stack = 0, [(r, c)]
                grid[r][c] = 0
                while stack:
                    cr, cc = stack.pop()
                    area += 1
                    for nr, nc in neighbours(cr, cc, rows, cols):
                        if grid[nr][nc] == 1:
                            grid[nr][nc] = 0
                            stack.append((nr, nc))
                best = max(best, area)
    return best

assert max_area_of_island([[0, 1, 1], [0, 1, 0], [1, 0, 0]]) == 3
assert max_area_of_island([[0, 0]]) == 0

6. Shortest path on a grid with BFS

Shortest path in a binary matrix from the top-left to the bottom-right through cells with value 0, moving in 8 directions. BFS by layers: the layer number is the distance.

def shortest_path_binary_matrix(grid):
    n = len(grid)
    if grid[0][0] or grid[n - 1][n - 1]:
        return -1
    queue = deque([(0, 0, 1)])                  # row, col, path length so far
    grid[0][0] = 1                              # mark visited
    while queue:
        r, c, d = queue.popleft()
        if r == n - 1 and c == n - 1:
            return d
        for dr in (-1, 0, 1):
            for dc in (-1, 0, 1):
                nr, nc = r + dr, c + dc
                if 0 <= nr < n and 0 <= nc < n and grid[nr][nc] == 0:
                    grid[nr][nc] = 1
                    queue.append((nr, nc, d + 1))
    return -1

assert shortest_path_binary_matrix([[0, 1], [1, 0]]) == 2
assert shortest_path_binary_matrix([[0, 0, 0], [1, 1, 0], [1, 1, 0]]) == 4
assert shortest_path_binary_matrix([[1, 0], [0, 0]]) == -1

Multi-source BFS. When many starting points spread simultaneously, put all of them in the queue at the start. Distance is then "the distance to the nearest source". Rotting oranges is the classic: all rotten oranges start in the queue, and each minute is one BFS layer.

def oranges_rotting(grid):
    rows, cols = len(grid), len(grid[0])
    queue, fresh = deque(), 0
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == 2:
                queue.append((r, c))
            elif grid[r][c] == 1:
                fresh += 1
    minutes = 0
    while queue and fresh:
        for _ in range(len(queue)):                    # one minute = one full layer
            r, c = queue.popleft()
            for nr, nc in neighbours(r, c, rows, cols):
                if grid[nr][nc] == 1:
                    grid[nr][nc] = 2
                    fresh -= 1
                    queue.append((nr, nc))
        minutes += 1
    return minutes if fresh == 0 else -1

assert oranges_rotting([[2, 1, 1], [1, 1, 0], [0, 1, 1]]) == 4
assert oranges_rotting([[2, 1, 1], [0, 1, 1], [1, 0, 1]]) == -1
assert oranges_rotting([[0, 2]]) == 0

The same idea solves walls and gates (distance from each room to the nearest gate) and 01 matrix: start from all the targets and expand outward, instead of searching from each cell.

7. Searching a state space: word ladder

Sometimes nodes are not given, but states, and edges are allowed moves. In word ladder, each word is a node, and two words are adjacent if they differ by one letter. Find the shortest transformation from a begin word to an end word.

def ladder_length(begin, end, word_list):
    words = set(word_list)
    if end not in words:
        return 0
    queue = deque([(begin, 1)])
    seen = {begin}
    while queue:
        word, steps = queue.popleft()
        if word == end:
            return steps
        for i in range(len(word)):
            for ch in "abcdefghijklmnopqrstuvwxyz":
                nxt = word[:i] + ch + word[i + 1:]
                if nxt in words and nxt not in seen:
                    seen.add(nxt)
                    queue.append((nxt, steps + 1))
    return 0

assert ladder_length("hit", "cog", ["hot", "dot", "dog", "lot", "log", "cog"]) == 5
assert ladder_length("hit", "cog", ["hot", "dot", "dog", "lot", "log"]) == 0

Time $O(N\cdot L\cdot 26)$ for $N$ words of length $L$ (building neighbours by changing each position). The skill here is recognising the graph and the BFS, and describing the state and the transitions.

8. DFS patterns beyond counting

Clone a graph. Copy nodes, keeping a map from original to clone so shared and cyclic structure is preserved.

class Node:
    def __init__(self, val, neighbors=None):
        self.val = val
        self.neighbors = neighbors or []

def clone_graph(node):
    if not node:
        return None
    clones = {}
    def copy(n):
        if n in clones:
            return clones[n]
        clones[n] = Node(n.val)
        for nb in n.neighbors:
            clones[n].neighbors.append(copy(nb))
        return clones[n]
    return copy(node)

a, b, c = Node(1), Node(2), Node(3)
a.neighbors, b.neighbors, c.neighbors = [b, c], [a, c], [a, b]
ca = clone_graph(a)
assert ca is not a and ca.val == 1 and sorted(n.val for n in ca.neighbors) == [2, 3]
assert ca.neighbors[0].neighbors[0] is ca               # the cycle is preserved

Pacific Atlantic water flow, surrounded regions: instead of searching from every cell, search backward from the boundary, marking everything that can reach it, then combine. It turns an $O((RC{)}^2)$ problem into $O(RC)$.

def surrounded_regions(board):
    rows, cols = len(board), len(board[0])
    def mark_safe(r, c):
        stack = [(r, c)]
        while stack:
            cr, cc = stack.pop()
            if 0 <= cr < rows and 0 <= cc < cols and board[cr][cc] == "O":
                board[cr][cc] = "S"                       # connected to the border: safe
                stack.extend([(cr + 1, cc), (cr - 1, cc), (cr, cc + 1), (cr, cc - 1)])
    for r in range(rows):
        mark_safe(r, 0); mark_safe(r, cols - 1)
    for c in range(cols):
        mark_safe(0, c); mark_safe(rows - 1, c)
    for r in range(rows):
        for c in range(cols):
            board[r][c] = "O" if board[r][c] == "S" else "X"
    return board

b = [list("XXXX"), list("XOOX"), list("XXOX"), list("XOXX")]
assert ["".join(row) for row in surrounded_regions(b)] == ["XXXX", "XXXX", "XXXX", "XOXX"]

9. Cycle detection and bipartite check

Detect a cycle in an undirected graph with DFS: a visited neighbour that is not your parent means a cycle. For directed graphs, track the nodes on the current DFS path (see the topological sort section of the next chapter).

def has_cycle_undirected(n, edges):
    graph = build_graph(edges)
    seen = set()
    def dfs(node, parent):
        seen.add(node)
        for nxt in graph[node]:
            if nxt == parent:
                continue
            if nxt in seen or dfs(nxt, node):
                return True
        return False
    return any(dfs(v, -1) for v in range(n) if v not in seen)

assert has_cycle_undirected(3, [(0, 1), (1, 2), (2, 0)]) is True
assert has_cycle_undirected(4, [(0, 1), (1, 2), (2, 3)]) is False

Is the graph bipartite? Try to 2-colour it with BFS. If an edge joins two same-coloured nodes, it is not bipartite (it has an odd cycle).

def is_bipartite(adj):
    color = {}
    for start in range(len(adj)):
        if start in color:
            continue
        color[start] = 0
        queue = deque([start])
        while queue:
            node = queue.popleft()
            for nxt in adj[node]:
                if nxt not in color:
                    color[nxt] = 1 - color[node]
                    queue.append(nxt)
                elif color[nxt] == color[node]:
                    return False
    return True

assert is_bipartite([[1, 3], [0, 2], [1, 3], [0, 2]]) is True
assert is_bipartite([[1, 2, 3], [0, 2], [0, 1, 3], [0, 2]]) is False

10. Choosing the traversal

11. Common mistakes

• Not marking visited, causing infinite loops or exponential time.
• Marking visited too late in BFS (on dequeue), which lets duplicates pile up in the queue.
• Wrong bounds checks in grids: check 0 <= r < rows before indexing.
• Forgetting disconnected components: loop over all nodes, not just one start.
• Using DFS for shortest path. DFS finds a path, not the shortest.
• Recursion depth on large grids or long chains in Python.
• Treating an undirected edge as one-way when building the adjacency list.
• Modifying the input grid when the caller needs it intact. Say so or copy.
• Complexity stated in $n$ when the real parameters are $V$ and $E$, or $R$ and $C$.

12. Practice set

1. Number of islands, max area of island, island perimeter, number of closed islands.
2. Flood fill, surrounded regions, pacific atlantic water flow.
3. Rotting oranges, walls and gates, 01 matrix.
4. Shortest path in a binary matrix, shortest bridge, minimum knight moves.
5. Word ladder, open the lock, minimum genetic mutation.
6. Clone graph, copy a graph with random pointers.
7. Is graph bipartite, possible bipartition.
8. Number of provinces (connected components in an adjacency matrix).
9. Find the town judge, find if a path exists in a graph.
10. All paths from source to target, keys and rooms.