Skip to content

BFS & DFS

Lesson 7 of 7 in Recursion, Trees & Graphs · 45 min · Intermediate

Explore ripple by ripple (BFS) or path by path (DFS).

Introduction

A rumour starts with one student. Every hour, everyone who knows it tells all their friends. Who hears it in hour 1, hour 2, hour 3?

Hour 1 is the starter's friends. Hour 2 is those friends' friends who haven't heard it yet. Each hour is one ring around the starter, and the hour you hear the rumour is exactly how many friendship steps you are from them.

Now explore a cave instead. Take a tunnel, then the next unexplored tunnel, then the next, until you hit a dead end. Only then do you walk back to the last fork and try the tunnel you skipped. Same tunnels, but a completely different order of visits.

Lesson overview

This lesson will show you how to:

  • Explain why BFS finds the fewest steps when every step costs the same.
  • Trace BFS on a grid, recording the distance to each cell as it spreads.
  • Trace DFS on a graph, backtracking when a branch has nothing new.
  • Implement one visit loop that switches between a queue and a stack.
  • Choose BFS for shortest hops, and reach for Dijkstra when steps have costs.

The picture

Grid: distance from S, written in each cell
S12#1#2Ecurpopped: being expanded nowfrontier: waiting in queuewalls are never enteredA grid of 3 rows by 4 columns. Row 0: S (visited), 1 (visited), 2 (compare), wall. Row 1: 1 (focus), wall, empty, empty. Row 2: 2 (compare), empty, empty, E. Columns: 0, 1, 2, 3. Pointers: cur at row 1, column 0.
Queue (front is next out)
queue0,202,01frontbackArray queue with 2 slots: 0,2, 2,0. Pointers: front at index 0; back at index 1.

Mental model

BFS is a ripple in a pond. It reaches everything one step away, then everything two steps away, then three, one full ring at a time.

DFS is a maze explorer trailing a ball of string. Follow one corridor as far as it goes, and at a dead end wind the string back to the last junction that still has a way you haven't tried.

Both pull the next cell off a to-do pile and never visit a cell twice. Take the oldest and you spread in rings; take the newest and you dive deep.

Words to know

BFS
Breadth-first search. Visit everything one step away, then everything two steps away, and so on. It keeps its to-do pile in a queue.
DFS
Depth-first search. Follow one path as far as it goes, then back up and try the next. Its to-do pile is a stack, or the recursion call stack.
frontier
The cells you have discovered but not explored yet. In BFS these are exactly the cells waiting in the queue.
visited set
A record of which cells you have already seen. Check it before queueing a cell so nothing is queued twice and a loop can't trap you.
queue vs stack
A queue hands back the oldest item (first in, first out). A stack hands back the newest (last in, first out). That one choice turns the same loop into BFS or DFS.
level
All the cells at the same distance from the start. BFS finishes one level completely before it starts the next.
shortest path (unweighted)
The path with the fewest steps when every step counts the same. BFS finds it because it reaches each cell by its fewest steps first. If steps have different costs, plain BFS can be wrong.
connected component
A group of nodes that can all reach each other. One search from any node visits exactly its component, so start a new search at each unvisited node to count components.

Watch it run

Step with → or Next. When a question pops up, make your guess. Try your own input once the guided run ends.

Getting the demo ready…

Recognise it

Most of the skill is noticing the clue in the problem statement.

Reach for it when

  • Yes: You need the fewest steps, moves or hops and every step costs the same: a maze, a word ladder, a knight's moves.
  • Yes: You must visit everything reachable from a start: count islands, flood-fill a region, find a connected group.
  • Yes: Something spreads outward from one or many places at once, minute by minute, like rotting oranges or the distance to the nearest 0.
  • Yes: The problem hides a graph: grid cells with four neighbours, words one letter apart, puzzle states one move apart.

Not this when

  • No: Steps have different costs, like roads with distances or flights with prices. Plain BFS counts steps, not total cost. That is weighted shortest path, so reach for Dijkstra, which swaps the queue for a heap.
  • No: You are picking the best answer from overlapping subproblems, like fewest coins or longest increasing run. Nothing is being searched, so dynamic programming fits.
  • No: You must build every subset or arrangement and undo choices as you go. That is backtracking: a recursion pattern that dives like DFS but explores choices, not a given graph.

Which pattern fits?

  1. Which pattern? 1 of 5

    Given a grid of '1' (land) and '0' (water), count how many separate islands there are.

  2. Which pattern? 2 of 5

    A road map gives the length of every road. Find the shortest total distance from city A to city B.

  3. Which pattern? 3 of 5

    Given two words and a dictionary, find the fewest single-letter changes that turn one word into the other, using only dictionary words.

  4. Which pattern? 4 of 5

    Given an array of distinct numbers, return every possible subset.

  5. Which pattern? 5 of 5

    You can climb 1 or 2 stairs at a time. How many different ways are there to reach the top of an n-step staircase?

The code

First the idea in plain steps. Then the same idea as real code, line for line.

Pseudocode
  1. 1dist = a table of −1 (−1 means not seen yet)
  2. 1dist[S] = 0, queue = [S]
  3. while the queue is not empty:
  4. 2cell = take the front of the queue
  5. 5if cell is E: return dist[cell]
  6. for each neighbour: up, right, down, left:
  7. 3if off the grid, a wall, or dist != −1: skip it
  8. 4dist[neighbour] = dist[cell] + 1
  9. 4add neighbour to the back of the queue
  10. 5return −1 (E was never reached)

The faint numbers are the rules in the Rule Rail under the stage. Same numbers, same order.

Getting the replay ready…

from collections import deque


def shortest_path(grid):
    rows, cols = len(grid), len(grid[0])
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == 'S':
                sr, sc = r, c
            if grid[r][c] == 'E':
                er, ec = r, c
    dist = [[-1] * cols for _ in range(rows)]
    dist[sr][sc] = 0
    queue = deque([(sr, sc)])
    while queue:
        r, c = queue.popleft()
        if (r, c) == (er, ec):
            return dist[r][c]
        for dr, dc in ((-1, 0), (0, 1), (1, 0), (0, -1)):
            nr, nc = r + dr, c + dc
            if nr < 0 or nr >= rows or nc < 0 or nc >= cols:
                continue
            if grid[nr][nc] == '#' or dist[nr][nc] != -1:
                continue
            dist[nr][nc] = dist[r][c] + 1
            queue.append((nr, nc))
    return -1
Time · O(R·C) on an R × C grid, or O(V + E) in a general graphSpace · O(R·C) for the distance table, or O(V) in a general graph
  • Stamp a cell when you queue it, not when you pop it. Stamping late lets several neighbours queue the same cell, which bloats the queue and can make the search far slower.
  • The dist table is both the answer and the visited set: −1 means unseen. It also leaves the input grid untouched. Many solutions overwrite the grid with a marker to save memory; that is only fine when you are allowed to change the input.
  • Space, precisely: the queue holds one frontier. On a tree that is O(width) for BFS against O(height) of recursion for DFS. On a general graph or grid the visited set is O(V) (O(R·C)) either way, so quote O(V) overall.
  • Swap the queue for a stack (or recursion) and you get DFS. It still visits each node once in O(V + E), but the first path it finds is not guaranteed to be shortest.
  • For several starting points, such as every rotten orange or every 0, put them all in the queue at distance 0 before the loop. That is multi-source BFS: one search, many ripples starting together.

Worked examples

Real interview problems, solved with the same recipe.

Open on LeetCode (opens in a new tab)

You are given an image as a grid of colours, a starting pixel (sr, sc) and a new colour. Repaint the starting pixel and every pixel connected to it up, down, left or right that has the same original colour. Return the repainted image.

Input

image = [[1,1,1],[1,1,0],[1,0,1]], sr = 1, sc = 1, color = 2

Output

[[2,2,2],[2,2,0],[2,0,1]]

Approach

  1. Remember the starting colour, old. The area to repaint is every pixel reachable from the start through pixels that still have the colour old.
  2. Recurse: repaint this pixel, then try the four neighbours. Stop at the edge or at any pixel whose colour is not old.
  3. If old already equals the new colour, return early. Otherwise a repainted pixel still looks like old and the recursion never stops.
  4. Work on a copy of the image so the caller's grid is not changed. The pixel at (2,2) is not connected to the start through 1s, so it stays 1.
def fill(image, r, c, old, color):
    rows, cols = len(image), len(image[0])
    if r < 0 or r >= rows or c < 0 or c >= cols:
        return
    if image[r][c] != old:
        return
    image[r][c] = color
    fill(image, r - 1, c, old, color)
    fill(image, r + 1, c, old, color)
    fill(image, r, c - 1, old, color)
    fill(image, r, c + 1, old, color)


def flood_fill(image, sr, sc, color):
    result = [row[:] for row in image]
    old = result[sr][sc]
    if old != color:
        fill(result, sr, sc, old, color)
    return result
Time · O(R·C)Space · O(R·C) for the recursion in the worst case

Knowledge check

Test yourself first. Try to answer these in your own words, then take the quiz below to check.

  1. You want the fewest steps from S to E in a maze where every step costs the same. Why does BFS find them?
  2. BFS pops a cell whose distance is 3 and finds an open neighbour that has not been seen. What gets written on that neighbour?
  3. DFS reaches E and stops. What do you know about the path it followed?
  4. What goes wrong if BFS marks a cell as seen only when it is popped, instead of when it is queued?
  5. Both BFS and DFS run on a general graph with V nodes. What extra memory do both need in the worst case?

Question 1 of 5

You want the fewest steps from S to E in a maze where every step costs the same. Why does BFS find them?

Assignment

Pick one, try it cold for ten minutes, then come back for the hint.

0 of 8 solved

  1. Solve Find if Path Exists in Graph (opens in a new tab) (LeetCode, easy)

    Hint: Build neighbour lists from the edges, then search from the source. If the destination ever gets visited, a path exists.

  2. Solve Max Area of Island (opens in a new tab) (LeetCode, medium)

    Hint: It is the island counter again, but each search also returns how many cells it used. Keep the biggest.

  3. Solve Shortest Path in Binary Matrix (opens in a new tab) (LeetCode, medium)

    Hint: Plain grid BFS, but a step may go to any of 8 neighbours. Count cells on the path, not moves between them.

  4. Solve 01 Matrix (opens in a new tab) (LeetCode, medium)

    Hint: Searching from every 1 is slow. Flip it: queue all the 0s at distance 0 and let one BFS ripple outward.

  5. Solve As Far from Land as Possible (opens in a new tab) (LeetCode, medium)

    Hint: Start the ripples from all land cells at once. The last water cell the BFS reaches is the farthest one.

  6. Solve Surrounded Regions (opens in a new tab) (LeetCode, medium)

    Hint: Ask which O cells can escape: those touching the border through other Os. Search inward from the border first, then flip what's left.

  7. Solve Pacific Atlantic Water Flow (opens in a new tab) (LeetCode, medium)

    Hint: Don't test every cell. Search uphill from each ocean's coast, then keep the cells both oceans reach.

  8. Solve Word Ladder (opens in a new tab) (LeetCode, hard)

    Hint: Words are nodes and one-letter changes are edges. Fewest changes is shortest path; generate neighbours by swapping each letter.

Additional resources