Know this before you start: “BFS with a queue, DFS with recursion”
Graph BFS and DFS
DFS goes as deep as it can before backing up (recursion or a stack). BFS spreads out in rings by distance (a queue) and finds shortest paths in unweighted graphs.
The idea
Both visit every reachable node once; they differ in order. DFS follows one path to its end, then backtracks: natural for “explore this whole island” or “is there any path?”.
BFS visits everything 1 step away, then 2 steps, and so on, using a queue. So the first time BFS reaches a node is by the fewest edges: shortest paths in unweighted graphs and grids.
See it step by step
Graph 1–2, 1–3, 2–4, start at 1
- DFS: 1 → 2 → 4 (dead end, back up) → 3
- BFS: 1, then its neighbours 2 and 3, then 4
- BFS reached 4 at distance 2, the shortest.
In code (Python)
from collections import deque
graph = {1: [2, 3], 2: [1, 4], 3: [1], 4: [2]}
def dfs(node, seen=None, order=None):
seen, order = seen or set(), order if order is not None else []
seen.add(node)
order.append(node)
for nxt in graph[node]:
if nxt not in seen:
dfs(nxt, seen, order)
return order
def bfs_distances(start):
dist = {start: 0}
queue = deque([start])
while queue:
node = queue.popleft()
for nxt in graph[node]:
if nxt not in dist:
dist[nxt] = dist[node] + 1
queue.append(nxt)
return dist
print(dfs(1)) # [1, 2, 4, 3]
print(bfs_distances(1)) # {1: 0, 2: 1, 3: 1, 4: 2}Both O(V + E) time and O(V) space.
When you'll use it
- DFS: islands, connected components, cycles, any path. BFS: shortest steps, nearest exit, rotting oranges, word ladder.
Common mistakes
- Using DFS for shortest paths.
- Marking visited on dequeue in BFS, so nodes are queued many times.
