PYTHON / DATA STRUCTURES AND ALGORITHMS
Breadth-first and depth-first search
Implement iterative BFS with a deque and DFS with a stack or recursion, and use BFS parent pointers to recover shortest paths in unweighted graphs.
What you will learn
- Write one traversal loop and switch behaviour by swapping the frontier structure
- Mark nodes seen at discovery time, not at pop time, to bound queue size
- Rebuild a shortest path from BFS parent pointers instead of storing whole paths
- Recognise when recursive DFS will hit Python's recursion limit
Understanding Breadth-first and depth-first search
A graph traversal keeps a frontier of discovered-but-unprocessed nodes. Take a node out, record it, and put its unseen neighbours in. Breadth-first search takes nodes out in the order they went in, using collections.deque and popleft, so it finishes every node at distance 1 from the start before touching anything at distance 2. Depth-first search takes out the most recently added node, using a plain list with pop or the interpreter's own call stack, so it walks as far down one branch as it can before backtracking.
That FIFO ordering is the entire reason BFS solves shortest paths on unweighted graphs. When BFS first reaches a node, no shorter route to it exists, because every route of length k was already expanded before any route of length k+1 was considered. So the first parent recorded for a node is a parent on a shortest path, and you recover the path by walking parent pointers back to the start and reversing. DFS gives no such guarantee: it reports whatever path it stumbled into first, which can be arbitrarily long.
Both run in O(V + E) time because each node enters the frontier once and each edge is inspected once from its endpoints. The seen set is what makes that true, and it is also what stops cycles from looping forever. Mark a node the moment you discover it, before it is popped; if you only mark on pop, a node with many predecessors can be queued once per predecessor, which wastes memory and repeats work even though the visit order stays correct.
from collections import deque
graph = {
'A': ['B', 'C'],
'B': ['D', 'E'],
'C': ['F'],
'D': [],
'E': ['F'],
'F': [],
}
def bfs(graph, start):
seen = {start}
frontier = deque([start])
order = []
while frontier:
node = frontier.popleft()
order.append(node)
for nbr in graph[node]:
if nbr not in seen:
seen.add(nbr)
frontier.append(nbr)
return order
def dfs(graph, start):
seen = set()
frontier = [start]
order = []
while frontier:
node = frontier.pop()
if node in seen:
continue
seen.add(node)
order.append(node)
for nbr in reversed(graph[node]):
frontier.append(nbr)
return order
print(bfs(graph, 'A'))
print(dfs(graph, 'A'))BFS and DFS share one traversal loop and differ only in whether the frontier is FIFO or LIFO, and that single difference is what gives BFS shortest paths.
Worked examples
Shortest path from BFS parent pointers
Stores one parent per node during BFS and reconstructs the shortest route by walking backwards.
from collections import deque
graph = {
1: [2, 3],
2: [4],
3: [4, 5],
4: [6],
5: [6],
6: [],
}
def shortest_path(graph, start, goal):
parent = {start: None}
frontier = deque([start])
while frontier:
node = frontier.popleft()
if node == goal:
break
for nbr in graph[node]:
if nbr not in parent:
parent[nbr] = node
frontier.append(nbr)
if goal not in parent:
return None
path = []
while goal is not None:
path.append(goal)
goal = parent[goal]
return path[::-1]
print(shortest_path(graph, 1, 6))
print(shortest_path(graph, 1, 5))Example explained
Line 1parent doubles as the seen set: membership means discovered, so no second dict is needed.
Line 2parent[nbr] = node is written only on first discovery, which is why it lands on a shortest route.
Line 3The start node maps to None, so the backward walk has a natural stopping condition.
Line 4path[::-1] reverses the backward chain into start-to-goal order.
Recursive DFS on a cyclic graph
Shows preorder against postorder and how the seen set keeps the cycle a -> b -> c -> a from recursing forever.
graph = {
'a': ['b'],
'b': ['c'],
'c': ['a', 'd'],
'd': [],
}
preorder = []
postorder = []
seen = set()
def dfs(node):
seen.add(node)
preorder.append(node)
for nbr in graph[node]:
if nbr not in seen:
dfs(nbr)
postorder.append(node)
dfs('a')
print(f"pre {preorder}")
print(f"post {postorder}")Example explained
Line 1seen.add(node) happens before the loop, so the edge c -> a finds a already marked and stops the cycle.
Line 2preorder appends on entry, giving the order nodes were discovered.
Line 3postorder appends after all descendants return, so a leaf like d lands first and the start node last.
Line 4The call stack replaces the explicit list frontier here; each pending frame is one node still open.
Important notes
BFS gives minimum hop count, not minimum cost. As soon as edges carry different weights you need Dijkstra instead.
Recursive DFS raises RecursionError at roughly 1000 nested calls, so a long chain of nodes needs the iterative stack version.
Common mistakes
Using a list with pop(0) for the BFS frontier: each removal shifts every remaining element, turning an O(V + E) traversal into quadratic time on wide graphs.
Marking nodes seen when they are popped instead of when they are discovered: a node with many predecessors gets queued once per predecessor, so the frontier grows far beyond V and neighbours are scanned repeatedly.
Trusting the first path DFS finds as the shortest one: on the graph 1 -> 2 -> 4 -> 6 with 1 -> 3 -> 4, DFS may report a longer route while BFS reports the minimum.
Try it yourself
Change, predict, then run
Take the graph from the main example and write a function that returns a dict mapping every reachable node to its distance in edges from 'A', using BFS and storing dist[nbr] = dist[node] + 1 at discovery. Verify that 'F' comes out as 2.
Open the Python workspaceCheck your understanding
In BFS over an unweighted graph, why must a node be added to the seen set when it is first discovered rather than when it is dequeued?
- Because the first time a node is reached it is already at its minimum distance, so later discoveries add nothing but let the same node be enqueued once per neighbour
- Because deque.popleft() removes the node before you can inspect it
- Because otherwise BFS would visit nodes in depth-first order
- Because a set cannot contain a node that is currently inside a deque
Show answer
The FIFO frontier expands all distance-k nodes before any distance-k+1 node, so the first arrival is already optimal and every subsequent arrival is redundant; marking late does not change the visit order, it only inflates the frontier. The depth-first option is wrong because traversal order is decided by popleft versus pop, not by when you mark nodes.