Graph BFS and DFS

Updated Nov 19, 2026 · 4 min read
On this page

    Graph search is tree search plus one rule: remember where you have been, because a graph can lead you back to a node you already saw. With a visited set, both DFS and BFS visit every node and edge once, O(V + E). DFS is the simplest way to explore everything reachable (count islands, clone a graph, find connected parts). BFS also tells you how far each node is, so it answers shortest-path questions on unweighted graphs.

    Graphs covers how to store a graph. This page covers searching one.

    When to recognise it

    • A grid of cells with "connected", "island", "region", "flood fill", "surrounded": a grid is a graph whose neighbours are up, down, left and right.
    • "Fewest steps / moves / minutes" where every step costs the same: BFS. Word ladder, knight moves, rotting oranges, shortest path in a binary matrix.
    • "Many starting points spreading at once": multi-source BFS. Put every source in the queue at distance 0.
    • "How many groups / components", "can A reach B", "clone this graph": DFS or BFS, whichever you write faster.
    • Weighted edges with "cheapest path": not plain BFS. Use Dijkstra, a BFS with a heap (see Heaps and Top-K).

    BFS: distance by rings

    BFS explores in rings: first everything one step away, then two, and so on. The first time it reaches a node is therefore along a shortest path.

    Graph A to F colored by distance from A: A is 0, B and C are 1, D and E are 2, F is 3. The queue moves through [A], [B, C], [D, E], [F]. D is reachable from both B and C but is queued once.
    Graph A to F colored by distance from A: A is 0, B and C are 1, D and E are 2, F is 3. The queue moves through [A], [B, C], [D, E], [F]. D is reachable from both B and C but is queued once.
    from collections import deque
    
    def shortest_path(graph, start, goal):
        """BFS on an unweighted graph: the first time we reach a node is the shortest distance."""
        dist = {start: 0}
        q = deque([start])
        while q:
            node = q.popleft()
            if node == goal:
                return dist[node]
            for nb in graph.get(node, []):
                if nb not in dist:          # mark on enqueue, not on dequeue
                    dist[nb] = dist[node] + 1
                    q.append(nb)
        return -1

    Time O(V + E), space O(V). Mark a node as visited (here, give it a distance) when you add it to the queue, not when you take it out. Otherwise the same node can be queued many times.

    DFS on a grid

    A 4 by 5 grid of 0s and 1s with three islands in three colors. Scanning every cell, each unvisited 1 starts a DFS that marks its whole island, so the number of DFS starts is 3.
    A 4 by 5 grid of 0s and 1s with three islands in three colors. Scanning every cell, each unvisited 1 starts a DFS that marks its whole island, so the number of DFS starts is 3.
    def count_islands(grid):
        """Grid DFS (iterative, so big grids don't hit the recursion limit). Mark visited when PUSHED."""
        rows, cols = len(grid), len(grid[0]) if grid else 0
        seen = set()
        islands = 0
        for r in range(rows):
            for c in range(cols):
                if grid[r][c] == '1' and (r, c) not in seen:
                    islands += 1
                    seen.add((r, c))
                    stack = [(r, c)]
                    while stack:
                        y, x = stack.pop()
                        for ny, nx in ((y + 1, x), (y - 1, x), (y, x + 1), (y, x - 1)):
                            if 0 <= ny < rows and 0 <= nx < cols and grid[ny][nx] == '1' and (ny, nx) not in seen:
                                seen.add((ny, nx))
                                stack.append((ny, nx))
        return islands

    This version uses an explicit stack, so a 1000 × 1000 grid of land does not hit Python's recursion limit. A recursive DFS is shorter and fine for small inputs; say which one you chose and why.

    Multi-source BFS

    When many cells spread at the same time (every rotten orange rots its neighbours each minute), start BFS from all of them at once. The queue then processes "minute 0" cells, then "minute 1" cells, exactly like levels in Tree BFS.

    from collections import deque
    
    def multi_source_minutes(grid):
        """Multi-source BFS (rotting oranges): start with ALL sources in the queue at distance 0."""
        rows, cols = len(grid), len(grid[0])
        q = deque((r, c, 0) for r in range(rows) for c in range(cols) if grid[r][c] == 2)
        fresh = sum(row.count(1) for row in grid)
        grid = [row[:] for row in grid]
        minutes = 0
        while q:
            r, c, m = q.popleft()
            minutes = max(minutes, m)
            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:
                    grid[nr][nc] = 2
                    fresh -= 1
                    q.append((nr, nc, m + 1))
        return minutes if fresh == 0 else -1

    Common bugs

    • No visited set, or marking visited on pop instead of push, which loops forever or does far too much work.
    • Bounds check after the array access: check 0 <= r < rows before grid[r][c].
    • Modifying the input grid to mark visited without saying so. It is a fine trick, but ask whether the input may be changed.
    • Using DFS for shortest paths. DFS finds a path, not the shortest one.
    • Forgetting disconnected parts: loop over every node or cell as a possible start, not just node 0.
    • Directed vs undirected: for an undirected edge list, add both directions to the adjacency list.

    Say this in the interview

    • "Each cell is a node with up to four neighbours, so this is a connected-components count. Every cell is visited once: O(rows × cols)."
    • "All moves cost the same, so BFS gives the shortest path. I mark nodes when I enqueue them so each one enters the queue once."

    Problems for this pattern

    1. Flood Fill: the simplest grid DFS.
    2. Number of Islands: count DFS starts.
    3. Clone Graph: DFS with a map from old node to new node.
    4. Rotting Oranges: multi-source BFS.
    5. Pacific Atlantic Water Flow: search backwards from both oceans.
    6. Shortest Path in Binary Matrix: BFS with 8 neighbours.
    7. Network Delay Time: Dijkstra, a BFS with a heap of distances.
    8. Word Ladder: BFS where the neighbours are one-letter changes.
    9. Evaluate Division: a weighted graph of ratios, DFS multiplies along the path.
    10. Web Crawler Multithreaded: BFS over links with a shared visited set.
    11. Bus Routes: BFS over routes, not stops.

    Related

    Graphs · Tree BFS · Topological Sort · Union-Find (another way to count components) · Heaps and Top-K (Dijkstra)