Graph BFS and DFS
Master the hidden trade‑offs between BFS and DFS, pick the optimal traversal for any interview graph problem, and avoid the classic bugs that trip candidates.
In interviews the real challenge isn’t recalling the textbook definition of BFS or DFS; it’s knowing which traversal silently saves you time, memory, and bugs. A subtle mistake—like enqueuing a node before marking it visited—can turn a linear‑time solution into an exponential nightmare. This guide shows the decision matrix, concrete step‑by‑step implementations, and advanced patterns that let you wield the right search every time.
01Decision matrix: picking BFS or DFS for the problem
Start by classifying the requirement. If you need the minimum number of edges between two vertices, BFS is unbeatable because the first time you dequeue the target you have the optimal distance (the MIT 6.006 notes prove this property). For pure connectivity, cycle detection, or topological ordering, DFS shines: its finishing times give a reverse‑postorder that is a valid topological sort for DAGs. Memory is another axis—BFS stores an entire frontier, which in a b‑ary tree can balloon to O(b^d) nodes, while DFS keeps only the current path (O(depth)). Dense graphs with high branching factor usually favor DFS because the frontier never explodes. Conversely, sparse graphs with a small branching factor keep BFS queues tiny, making BFS both fast and easy to reason about. The matrix below helps you translate these attributes into a concrete choice.
02BFS step‑by‑step implementation
A robust BFS begins by pushing the source into a deque and marking it visited before any neighbor is enqueued; this prevents the same node from entering the queue multiple times. While the queue isn’t empty, pop the leftmost element, process it, then push all unvisited neighbours, incrementing a distance map. Early termination is as simple as if node == target: return distance[node]. Below is a concrete run on a graph 0–1–2, 0–3, 3–4. Starting from 0, the queue evolves as [(0)] → [(1,3)] → [(2,4)]. After two levels, node 4 is reached with distance 2, confirming the shortest‑path property. The algorithm runs in O(V+E) time on adjacency‑list graphs (Wikipedia) and uses O(V) extra space for the visited set and queue.
from collections import deque
def bfs_shortest_path(adj, start, target):
visited = set([start])
dist = {start: 0}
q = deque([start])
while q:
node = q.popleft()
if node == target:
return dist[node]
for nb in adj[node]:
if nb not in visited:
visited.add(nb)
dist[nb] = dist[node] + 1
q.append(nb)
return -1 # unreachable
# Example graph
adj = {0: [1, 3], 1: [0, 2], 2: [1], 3: [0, 4], 4: [3]}
print(bfs_shortest_path(adj, 0, 4)) # prints 203DFS step‑by‑step implementation (recursive vs iterative)
Recursive DFS is elegant but hits Python’s recursion limit on deep graphs (>10⁴ depth). The iterative version replaces the call stack with a list acting as a stack, storing (node, iterator_index) pairs to simulate entry and exit. Marking a node when it is first popped (pre‑visit) prevents re‑pushing it from another branch, which is essential for correct cycle detection in directed graphs. Post‑visit actions—like appending to a order list—produce reverse‑postorder needed for topological sort. The example below runs DFS on a directed graph 0→1→2, 0→3→2. The stack sequence shows how node 2 is discovered from two parents but processed only once, and the final order list [2,1,3,0] is the reverse finishing order, ready for topological sorting.
def iterative_dfs(adj, start):
visited = set()
stack = [(start, 0)] # (node, next_child_index)
order = []
while stack:
node, idx = stack[-1]
if node not in visited:
visited.add(node) # pre‑visit
children = adj.get(node, [])
if idx < len(children):
# explore next child
stack[-1] = (node, idx + 1)
child = children[idx]
if child not in visited:
stack.append((child, 0))
else:
# all children processed – post‑visit
order.append(node)
stack.pop()
return order
adj = {0: [1, 3], 1: [2], 2: [], 3: [2]}
print(iterative_dfs(adj, 0)) # prints [2, 1, 3, 0]04Common pitfalls that trip interviewees
1️⃣ Stale visited set – When a problem asks for multiple queries on the same graph (e.g., many shortest‑path calls), re‑using the same visited without clearing it yields false negatives. Always instantiate a fresh set or reset it between runs. 2️⃣ Level counting errors – Beginners often increment a global counter inside the node‑processing loop, producing a distance that is one step too large. The correct pattern is to store distances per node (as shown in the BFS code) or process the queue level‑by‑level using a for _ in range(len(q)) loop. 3️⃣ Recursion depth – A DFS on a line graph of 10⁵ nodes crashes in Python. Switch to the iterative stack version or increase the recursion limit cautiously (sys.setrecursionlimit). 4️⃣ Mutating adjacency – Removing edges while iterating over a neighbor list leads to skipped nodes or runtime errors. Clone the list (for nb in list(adj[node]): …) if you need to modify it. These bugs are the most frequent reasons a candidate’s solution passes the sample but fails hidden tests.
05Advanced patterns built on BFS/DFS
Multi‑source BFS starts with all sources in the queue; distances then represent the nearest source. The classic "rotting oranges" problem uses this to spread infection level‑by‑level. Bidirectional BFS halves the search space for a single‑source‑single‑target query: alternate one step from the forward frontier and one from the backward frontier until they intersect. The node count drops from O(b^d) to O(b^{d/2}) (Wikipedia). For directed acyclic graphs, a DFS that records finishing times and then reverses the order yields a topological sort—guaranteed by the reverse post‑order property (MIT notes). Kosaraju’s algorithm runs two DFS passes (first on the original graph to compute finishing times, second on the reversed graph) to extract strongly connected components in O(V+E). Below is a concise bidirectional BFS that returns the length of the shortest path or -1 if none exists.
def bidirectional_bfs(adj, start, goal):
if start == goal:
return 0
front_start = {start}
front_goal = {goal}
visited_start = {start}
visited_goal = {goal}
dist = 0
while front_start and front_goal:
if len(front_start) > len(front_goal):
front_start, front_goal = front_goal, front_start
visited_start, visited_goal = visited_goal, visited_start
next_front = set()
dist += 1
for node in front_start:
for nb in adj[node]:
if nb in visited_goal:
return dist
if nb not in visited_start:
visited_start.add(nb)
next_front.add(nb)
front_start = next_front
return -106Testing, debugging, and visualizing traversals
Start with the smallest graph that reproduces a bug: a single edge, a triangle, or a disconnected pair. Print the order of nodes as they are dequeued (BFS) or popped (DFS) to verify that the algorithm follows the intended pattern. For BFS, also dump the distance map after each level; for DFS, output entry/exit timestamps to ensure correct post‑visit ordering. Unit‑test frameworks like unittest or pytest let you assert exact distances (assert bfs(adj,0,3)==2) and detect cycles (assert has_cycle(adj)). Visualization tools such as NetworkX with Matplotlib or online graph visualizers can animate the frontier expansion, making it trivial to spot a missing visited flag. By automating these checks you eliminate the hidden edge‑case failures that usually surface only in the interviewer's hidden test suite.
07BFS vs DFS: quick contrast checklist
Use BFS when you need the minimal number of edges between two nodes, when the graph is relatively shallow or has low branching factor, or when you must process nodes level‑by‑level (e.g., "Number of Islands", Word Ladder). BFS guarantees optimal distance on unweighted graphs and its queue never exceeds the width of the current frontier. Use DFS when you care about exploring a path to its depth, need to detect cycles in directed graphs, or must produce a topological ordering. DFS’s stack (or recursion) holds at most the depth of the graph, making it memory‑efficient for deep, skinny structures. If recursion depth is a concern, switch to an explicit stack. When both time and memory are tight, evaluate the graph’s branching factor: high‑branching favors DFS, low‑branching favors BFS. This checklist eliminates the guesswork that often leads candidates to pick the wrong traversal.
08Common interview questions
How do you find the shortest path in an unweighted graph?
Run BFS from the source, mark nodes visited on enqueue, and store a distance map; the first time you dequeue the target you have the optimal number of edges.
How can you detect a cycle in a directed graph?
Perform DFS while maintaining a recursion‑stack (or color map). If you encounter a node that is already in the current stack, a cycle exists.
When is bidirectional BFS worth implementing?
When you have a single source and a single target in a large, unweighted graph; it reduces explored nodes from O(b^d) to O(b^{d/2}), often cutting runtime in half.
What is the standard way to produce a topological order?
Run DFS, record nodes on post‑visit, then reverse the list; the reverse post‑order is a valid topological sort for any DAG.