Breadth-First & Depth-First Search
Learn how BFS and DFS explore graphs step by step, why one finds the shortest path and the other uses barely any memory, and build both from scratch in pure Python.
Imagine you're lost in a maze. One strategy: explore every corridor one step at a time, fanning outward like ripples in a pond. Another: pick a corridor and charge down it as far as it goes before trying anything else. These two instincts — spread wide vs. dive deep — are exactly what Breadth-First Search (BFS) and Depth-First Search (DFS) do. They power Google Maps routing, social-network friend suggestions, game AI, and web crawlers.
Both algorithms operate on a graph — nodes (places) connected by edges (paths between them). In Python, a graph is just a dictionary where each key maps to a list of neighbours. The goal: start at one node, find all others (or a specific target). The difference between BFS and DFS is entirely in which node you visit next.
A Queue vs. a Stack of Books
Both algorithms share the same skeleton: a frontier (nodes you plan to visit), a visited set (nodes already seen), and a loop. The loop pulls one node off the frontier, processes it, and adds its unvisited neighbours.
BFS uses a queue (FIFO). Like a checkout line: the person who arrived first leaves first. You always process the oldest task — finishing every node at distance 1 before moving to distance 2. A perfect ripple.
DFS uses a stack (LIFO). Like a pile of books: you grab the top one. The newest task is processed immediately, dragging you deeper and deeper down one branch before you ever backtrack.
#BFS: Rippling Outward
from collections import deque
graph = {
'A': ['B', 'C'],
'B': ['D', 'E'],
'C': ['F'],
'D': [], 'E': [], 'F': []
}
def bfs(graph, start):
visited = set([start])
queue = deque([start]) # FIFO: oldest node dequeued first
order = []
while queue:
node = queue.popleft()
order.append(node)
for nb in graph[node]:
if nb not in visited:
visited.add(nb)
queue.append(nb)
return order
print(bfs(graph, 'A'))#DFS: Diving Deep
graph = {
'A': ['B', 'C'],
'B': ['D', 'E'],
'C': ['F'],
'D': [], 'E': [], 'F': []
}
def dfs(graph, start):
visited = set([start])
stack = [start] # LIFO: newest node popped first
order = []
while stack:
node = stack.pop()
order.append(node)
for nb in graph[node]:
if nb not in visited:
visited.add(nb)
stack.append(nb)
return order
print(dfs(graph, 'A'))BFS finds the shortest path. Because BFS finishes every node at distance k before moving to k+1, the first time it reaches a target it has taken the fewest possible steps. Track this with a parent dictionary that records how you arrived at each node. When the goal is found, walk backwards through parent to reconstruct the full path. In a weighted graph (edges with different costs) you'd use Dijkstra's algorithm instead — but for unweighted graphs, BFS gives you the shortest path for free.
from collections import deque
graph = {
'A': ['B', 'C'], 'B': ['D', 'E'],
'C': ['F'], 'D': [], 'E': [], 'F': []
}
def bfs_path(graph, start, goal):
parent = {start: None}
queue = deque([start])
while queue:
node = queue.popleft()
if node == goal:
path, n = [], goal
while n is not None:
path.append(n)
n = parent[n]
return list(reversed(path))
for nb in graph[node]:
if nb not in parent:
parent[nb] = node
queue.append(nb)
return None
print(bfs_path(graph, 'A', 'F'))#Trade-offs: When to Use Which
| | BFS | DFS | |---|---|---| | Frontier | Queue (FIFO) | Stack (LIFO) | | Explores | Level by level | Deep branch first | | Shortest path? | Yes (unweighted) | Not guaranteed | | Memory use | High — holds whole frontier | Low — only current path | | Best for | Shortest-path, guaranteed answer | Cycle detection, topological sort, deep mazes |
BFS is complete (always finds a solution if one exists) and optimal (shortest path first), but the frontier can balloon in wide graphs — in a social network, millions of people sit just 1 hop away. DFS is memory-lean since it only keeps the path to the current node, but it can chase a very long wrong branch and never guarantees the optimal solution.
Always track visited nodes!
Forgetting the visited set is the most common BFS/DFS bug. In a graph with cycles (A → B → A → B → ...) you'll loop forever. Both algorithms need the visited set to ensure each node is processed at most once. Build the habit even when you think your graph is a tree — cycle protection costs almost nothing.
Real libraries in production
In production code, NetworkX (pip install networkx) provides nx.bfs_edges(), nx.dfs_edges(), and nx.shortest_path(). Building from scratch here reveals the mechanics — in real projects, reach for the library.
You're building a 'six degrees of separation' feature that finds the shortest friendship chain between two users. Which algorithm should you use, and why?
You now have the full picture. Both BFS and DFS use a frontier, a visited set, and a loop. Swap a queue for a stack and you transform the entire search strategy — from ripple to dive. This one-data-structure insight reappears in AI planning, compiler design, game-tree search, and network analysis. Master these two algorithms and you've built the foundation for nearly every path-finding and exploration problem you'll encounter.
Key takeaways
- BFS uses a queue (FIFO) to explore level by level, guaranteeing the shortest path in an unweighted graph.
- DFS uses a stack (LIFO) to dive deep first — memory-efficient but does not guarantee the shortest path.
- Both algorithms share the same skeleton: a frontier, a visited set, and a loop. The only difference is the data structure.
- Always maintain a visited set to prevent infinite loops in graphs with cycles.
- Use BFS when you need the shortest path; use DFS when memory is tight or you need to explore deep structure.
BFS explores evenly in all directions (a queue) — it always finds the shortest path.
This BFS explores a graph level by level from the start node. What does it print?
from collections import deque
graph = {
'S': ['A', 'B'],
'A': ['C'],
'B': ['C'],
'C': []
}
def bfs(graph, start):
visited = set([start])
queue = deque([start])
order = []
while queue:
node = queue.popleft()
order.append(node)
for nb in graph[node]:
if nb not in visited:
visited.add(nb)
queue.append(nb)
return order
print(bfs(graph, 'S'))This code has a bug — what's wrong?
from collections import deque
def bfs(graph, start):
visited = set([start])
queue = deque([start])
order = []
while queue:
node = queue.pop() # take the next node
order.append(node)
for nb in graph[node]:
if nb not in visited:
visited.add(nb)
queue.append(nb)
return orderComplete this DFS. It should dive deep by always processing the most recently added node — the newest item on the stack.
def dfs(graph, start): visited = set([start]) stack = [start] order = [] while stack: node = stack.() # LIFO: newest node first order.append(node) for nb in graph[node]: if nb not in visited: visited.add(nb) stack.append(nb) return order
Put these lines in the correct order to reconstruct the shortest path once BFS reaches the goal, by walking backwards through the parent dictionary.
path, n = [], goal
path.append(n)
while n is not None:
n = parent[n]
return list(reversed(path))
A dungeon is represented as a dictionary where each room name maps to a list of adjacent rooms. Write a function find_exit(dungeon, start, exit_room) that uses BFS to find the shortest path from start to exit_room. Return the path as a list of room names, or an empty list if no path exists.
Expected outputs: - find_exit(dungeon, 'Entrance', 'Exit') → ['Entrance', 'Hall', 'Garden', 'Exit'] - find_exit(dungeon, 'Entrance', 'Treasure') → ['Entrance', 'Hall', 'Armory', 'Treasure'] - find_exit(dungeon, 'Crypt', 'Exit') → ['Crypt', 'Entrance', 'Hall', 'Garden', 'Exit']
Try it live — edit the code and hit Run to execute real Python: