Agents & Search›Extra· 40 min read

Search Algorithms: BFS & DFS

Two basic ways to explore a state space — breadth-first finds the shortest path; depth-first dives deep.

What you will learn

Explain BFS vs DFS
Run BFS on a small graph to find a path
Know which to pick and why

Two ways to explore

	Breadth-First (BFS)	Depth-First (DFS)
How it explores	Level by level, nearest first	Dives down one path to the end
Finds shortest path?	Yes (in number of steps)	Not guaranteed
Memory use	More (holds a whole level)	Less
Uses a	Queue (first in, first out)	Stack / recursion

BFS that returns the actual path

Using the maze graph from the last lesson, BFS explores outward from the start until it reaches the goal, remembering how it got to each cell so it can rebuild the path.

Step by step, BFS works like this:

Start a queue (a waiting line — first in, first out) holding just the starting path, e.g. [A], and mark A as seen.
Take the oldest path off the front of the queue and look at its last cell.
Goal check: if that cell is the goal, you are done — return this path.
Otherwise, for each unseen neighbour, mark it seen and add a new, longer path (old path + neighbour) to the back of the queue.
Repeat from step 2 until the goal is found, or the queue is empty (which means no path exists).

Breadth-first search returning the shortest path through the maze

from collections import deque

def bfs(graph, start, goal):
    queue = deque([[start]])      # a queue of paths
    seen = {start}
    while queue:
        path = queue.popleft()    # take the oldest path (breadth-first)
        node = path[-1]
        if node == goal:
            return path           # found it
        for nxt in graph[node]:
            if nxt not in seen:
                seen.add(nxt)
                queue.append(path + [nxt])
    return None                   # no path exists

maze = {'A':['B'], 'B':['A','C','D'], 'C':['B'], 'D':['B','E'], 'E':[]}
print(bfs(maze, 'A', 'E'))

Note: Output: ['A', 'B', 'D', 'E'] BFS found the shortest route A → B → D → E. The “seen” set stops it revisiting cells and looping forever.

Watch out: Never forget the visited / seen set. With a loop in the graph (A→B→A…), an algorithm without it will run forever.

Swap the queue for a stack (take the newest path instead of the oldest) and the very same code becomes depth-first search.

Tip: Rule of thumb: need the shortest path and have enough memory? Use BFS. Just need any path with little memory? DFS. Want shortest and fast on big maps? You need a smarter, guided search — next lesson.

Q. Why does BFS find the shortest path (in steps) but DFS may not?

Answer: BFS expands states in order of distance from the start, so the first time it meets the goal it has used the fewest steps. DFS may plunge down a long branch first.

✍️ Practice

Trace, on paper, the queue contents as bfs(maze, "A", "E") runs.
Change the maze so the shortest path is A → B → C and confirm BFS returns it.

🏠 Homework

Rewrite bfs as dfs by using a stack (pop the last path) and compare the path it returns.