Use breadth-first search when you need the fewest steps or anything about levels, because it reaches each node along a shortest path when every edge costs the same. Use depth-first search for reachability, cycles, ordering and exploring every path, because it is shorter to write and uses memory only for the current path. Both cost O(V + E) time.
BFS and DFS compared
| Breadth-first search | Depth-first search | |
|---|---|---|
| Explores | In rings of distance from the start | One path as far as it goes, then backs up |
| Uses | A queue | A stack, or recursion |
| Time | O(V + E) | O(V + E) |
| Space on a graph | O(V) | O(V) |
| Space on a tree | O(w), the widest level | O(h), the height |
| Shortest path, equal edge costs | Yes, the first arrival is shortest | No |
| Cycle detection, topological order | Possible, by counting incoming edges | Natural, by tracking the current path |
| Every path or combination | Awkward | Natural: this is backtracking |
| Easiest to write | A few more lines | Very short when recursive |
A worked example where both apply
Given a grid of open cells (0) and walls (1), can you get from the top-left to the bottom-right? Both searches answer that with the same seen set and the same neighbor loop. The only structural difference is the end of the list you take the next cell from.
from collections import deque
def neighbors(grid, r, c):
for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
nr, nc = r + dr, c + dc
if 0 <= nr < len(grid) and 0 <= nc < len(grid[0]) and grid[nr][nc] == 0:
yield nr, nc
def reachable_dfs(grid):
goal = (len(grid) - 1, len(grid[0]) - 1)
seen, stack = {(0, 0)}, [(0, 0)]
while stack:
cell = stack.pop() # the newest cell: go deep
if cell == goal:
return True
for nxt in neighbors(grid, *cell):
if nxt not in seen:
seen.add(nxt)
stack.append(nxt)
return False
def fewest_steps_bfs(grid):
goal = (len(grid) - 1, len(grid[0]) - 1)
seen, queue = {(0, 0)}, deque([((0, 0), 0)])
while queue:
cell, dist = queue.popleft() # the oldest cell: go level by level
if cell == goal:
return dist # the first arrival is the shortest
for nxt in neighbors(grid, *cell):
if nxt not in seen:
seen.add(nxt)
queue.append((nxt, dist + 1))
return -1For "can I get there," either is correct, with O(r · c) time and space. Change the question to "in how few moves," and only BFS still works as written: DFS would return the length of whichever path it found first, not the shortest.
Which to pick in an interview, and how to say why
- Fewest steps or levels: BFS. This is the one case where the choice is forced.
- Reachability, connected regions, flood fill: either, so pick the one you can write cleanly. Mention that recursive DFS can hit a recursion limit on a large grid.
- Every path, or the structure of the path: DFS, because it carries the current path as it goes.
- A very wide tree with a shallow answer: BFS finds it sooner. A very deep, narrow tree: BFS uses less memory there, and DFS holds the whole depth.
I need the fewest moves and every move costs the same, so I'll use breadth-first search: it explores in rings, so the first time I reach the goal is along a shortest path. Depth-first would find a path but not necessarily the shortest one. It's O(r times c) time and space, since each cell is queued at most once, and I mark cells as seen when I queue them so they're never added twice.