Breadth-First and Depth-First Search

This notebook compares BFS and DFS on the same grid world. Both algorithms explore reachable states, but the data structure used for the frontier changes the order of exploration and the path that is returned.

Notebook overview

Run the cells from top to bottom. The notebook has four parts:

  1. Build and display a connected grid map.
  2. Explore it with breadth-first search.
  3. Explore it with iterative depth-first search.
  4. Express depth-first search recursively.

Visual legend

  • Gray: wall
  • White: open state
  • Green: start
  • Red: goal
  • Yellow: visited state
  • Cyan: state currently being expanded

All three searches use the same map, start state, goal state, neighbor order, and drawing helpers. This makes their exploration patterns directly comparable.

Imports and shared constants

NumPy stores the grid and visited arrays. Matplotlib draws the map and the intermediate search states. A wall is represented by "#"; an open cell is represented by ".".

import numpy as np
import matplotlib.pyplot as plt

WALL = "#"
EMPTY = "."

figure_size = 1.5

Generate a connected map

generate_map first samples walls and open cells, then removes one wall from any completely blocked 2-by-2 region. It next uses union-find, also called the disjoint-set data structure, to track which open cells belong to the same connected component.

  • find(x) follows parent links to obtain a component representative and shortens future searches with path compression.
  • union(x, y) joins the components containing two neighboring open cells.
  • A wall is removed when its open neighbors belong to different components, allowing those components to be connected.

For a visual introduction to the data structure, see Princeton Algorithms’ Union-Find case study.

def generate_map(width, height, seed):
    np.random.seed(seed)
    m = np.random.choice([WALL, EMPTY], size=(height, width))
    # scan all 2x2 blocks and remove walls that are not needed
    for i in range(height - 1):
        for j in range(width - 1):
            block = m[i : i + 2, j : j + 2]
            if np.sum(block == WALL) == 4:
                # randomly remove one wall
                block[np.random.randint(2), np.random.randint(2)] = EMPTY
    # run union-find to make sure the map is connected
    parent = np.arange(width * height)

    def find(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]
            x = parent[x]
        return parent[x]

    def union(x, y):
        parent[find(x)] = find(y)

    for i in range(height):
        for j in range(width):
            if m[i, j] == WALL:
                continue
            for ni, nj in [(i + 1, j), (i, j + 1)]:
                if ni < height and nj < width and m[ni, nj] == EMPTY:
                    union(i * width + j, ni * width + nj)
    for i in range(height):
        for j in range(width):
            if m[i, j] == WALL:
                # check if all neighbors of this wall are connected
                # if not, remove this wall
                neighbors = []
                for ni, nj in [(i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1)]:
                    if 0 <= ni < height and 0 <= nj < width and m[ni, nj] == EMPTY:
                        neighbors.append(
                            find(ni * width + nj)
                        )  # get the parent of all empty neighbors
                if len(neighbors) != 0 and len(set(neighbors)) != 1:
                    m[i, j] = EMPTY
                    # connect all neighbors
                    for k in range(1, len(neighbors)):
                        union(neighbors[k - 1], neighbors[k])
    return m

Choose the start and goal

find_start_end repeatedly samples two grid coordinates until both are open cells. The same start and end values are reused by every search algorithm below.

def find_start_end(m):
    # randomly find a start and end point
    h, w = m.shape
    start = np.random.randint(h), np.random.randint(w)
    end = np.random.randint(h), np.random.randint(w)
    while m[start] == WALL or m[end] == WALL:
        start = np.random.randint(h), np.random.randint(w)
        end = np.random.randint(h), np.random.randint(w)
    return start, end

Draw the grid

show_map draws one rectangle per cell, adds row and column indices, preserves square cells with an equal aspect ratio, and hides the ordinary plot axes.

def show_map(m, ax=None):
    h, w = m.shape
    for i in range(h):
        for j in range(w):
            # draw a rectangle
            ax.add_patch(
                plt.Rectangle(
                    (j, h - i - 1), 1, 1, fc="gray" if m[i, j] == WALL else "white"
                )
            )
            # draw the border
            ax.add_patch(
                plt.Rectangle((j, h - i - 1), 1, 1, fill=False, edgecolor="black")
            )
    # draw indices of horizontal and vertical axis
    for i in range(h):
        ax.text(-0.5, h - i - 0.5, str(i), ha="center", va="center")
    for j in range(w):
        ax.text(j + 0.5, h + 0.5, str(j), ha="center", va="center")
    ax.set_xlim(-0.3, w + 0.3)
    ax.set_ylim(-0.3, h + 0.3)
    ax.set_aspect("equal", adjustable="box")
    ax.axis("off")

Draw a returned path

draw_path first draws the grid, colors the two endpoints, and then connects consecutive coordinates in path. It expects the path to be ordered from the start state to the goal state.

def draw_path(m, path, ax):
    h, w = m.shape
    last = path[0]
    show_map(m, ax)
    # draw the start and end points by filling the grid with a different color
    ax.add_patch(plt.Rectangle((last[1], h - last[0] - 1), 1, 1, fc="green"))
    ax.add_patch(plt.Rectangle((path[-1][1], h - path[-1][0] - 1), 1, 1, fc="red"))
    for i, j in path[1:]:
        # connect the two points
        ax.plot([last[1] + 0.5, j + 0.5], [h - last[0] - 0.5, h - i - 0.5], "r", lw=2)
        last = (i, j)

Build the example problem

The fixed random seed makes the map reproducible. The saved figure below shows the exact problem used by BFS and both DFS implementations.

# a = generate_map(5, 3, 1)
a = generate_map(6, 5, 2)
start, end = find_start_end(a)
# create a figure
fig, ax = plt.subplots(figsize=(figure_size, figure_size))
show_map(a, ax)
# plot the start and end points
ax.add_patch(
    plt.Circle((start[1] + 0.5, a.shape[0] - start[0] - 0.5), 0.3, color="green")
)
ax.add_patch(plt.Circle((end[1] + 0.5, a.shape[0] - end[0] - 0.5), 0.3, color="red"))
plt.show()

Comparison and discussion

Question BFS Iterative DFS Recursive DFS
Frontier discipline FIFO queue LIFO stack Python call stack
Shortest path with equal step costs? Yes No No
Sensitive to neighbor order? Yes Yes Yes
Main depth risk Broad frontier Deep branch Deep branch and recursion limit

Check your understanding

  1. Why does marking a state visited when it enters the frontier avoid duplicate work?
  2. Which single line changes FIFO behavior into LIFO behavior?
  3. Why can two correct DFS implementations return different paths?
  4. What happens if a goal is unreachable and path reconstruction assumes it was found?
  5. How would a deque change the BFS implementation without changing the algorithm?
Answers and discussion
  1. Mark on discovery. Once a state is marked, another parent cannot add it again. Each reachable state enters the frontier at most once, avoiding repeated expansion and conflicting parent assignments. This is appropriate for this unweighted BFS/DFS example; weighted shortest-path search needs different cost bookkeeping.
  2. Change which end is removed. Replacing i, j = q.pop(0) with i, j = q.pop() changes the same list from FIFO to LIFO. The iterative DFS code calls its list s, but the name is not what changes the behavior.
  3. DFS depends on traversal order. Recursive DFS immediately follows the first eligible neighbor, whereas pushing neighbors onto a stack makes the last pushed neighbor run first. Different ordering or discovery timing can produce different parent trees and valid paths. Neither version promises a shortest path.
  4. Reconstruction can fail or never terminate. Here the unused parent entries contain (0, 0). Starting from an unreachable goal can follow those defaults, produce an invalid path, or loop at (0, 0). Check that the goal was reached and return None or an empty path before reconstructing; the drawing helper must also handle failure.
  5. Use efficient queue removal. Import deque, initialize q = deque([start]), and replace q.pop(0) with q.popleft(). Keep append for insertion. FIFO order and the returned shortest-path length stay the same, while removal avoids shifting all remaining list elements.

Summary

BFS and DFS share most of their machinery. The frontier discipline controls exploration order, completeness behavior, memory use, and whether the first discovered path is guaranteed to be shortest.