Breadth-First and Depth-First Search

Queue or stack

Uninformed algorithms know nothing about where the goal lies. Breadth-first search (BFS) uses a queue: it expands states in order of distance from the start, so with equal step costs it finds a shortest path, but it can use a lot of memory. Depth-first search (DFS) uses a stack: it dives down one branch first, uses little memory, and may find a solution quickly, but the path it returns can be far from shortest and it can get lost in deep or infinite spaces. Uniform-cost search generalises BFS to unequal step costs.

BFS versus DFS on a grid, run

I ran this with plain Python 3 (standard library only), with fixed random seeds where randomness is used. On an 8x12 grid with a wall, BFS finds the shortest path of 18 steps after expanding 91 cells. DFS expands fewer cells (72) here but returns a path of 26 steps, longer than necessary.

from collections import deque
grid = ["S...........",
        "............",
        "......#.....",
        "......#.....",
        "......#.....",
        "......#.....",
        "......#.....",
        "...........G"]
R, C = len(grid), len(grid[0])
start = (0, 0); goal = (7, 11)
def neighbours(r, c):
    for dr, dc in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
        nr, nc = r + dr, c + dc
        if 0 <= nr < R and 0 <= nc < C and grid[nr][nc] != "#":
            yield nr, nc
def search(frontier_pop):
    frontier, parent, expanded = deque([start]), {start: None}, 0
    while frontier:
        node = frontier_pop(frontier); expanded += 1
        if node == goal:
            path, n = [], node
            while n: path.append(n); n = parent[n]
            return len(path) - 1, expanded
        for nb in neighbours(*node):
            if nb not in parent:
                parent[nb] = node; frontier.append(nb)
for name, pop in [("breadth-first", deque.popleft), ("depth-first", deque.pop)]:
    steps, expanded = search(pop)
    print(f"{name:<14} path length {steps:>2} | nodes expanded {expanded}")

Output:

breadth-first  path length 18 | nodes expanded 91
depth-first    path length 26 | nodes expanded 72

Track visited states

Without a visited set, both algorithms revisit states endlessly in graphs with cycles.

Quick check: Which algorithm guarantees a shortest path when all steps cost the same?

• Depth-first search
• Breadth-first search
• Random walk
• Hill climbing