Graph Traversal: BFS and DFS
BFS and DFS on a small graph, run step by step: visit order, shortest path in unweighted graphs, islands, topological sort, cycle detection, and the Python recursion limit trap.
BFS visits a graph level by level with a queue, so it finds shortest paths in unweighted graphs. DFS goes as deep as possible before backing up, using a stack or recursion, and suits cycle detection, topological sort and connected components. Both run in O(V + E) time. Interviewers expect nodes to be marked seen when queued, not when popped.
BFS visits a graph level by level using a queue and finds shortest paths in unweighted graphs. DFS goes as deep as it can before backing up, using a stack or recursion, and suits cycle detection, topological ordering and connected components. Both run in O(V + E). Recursive DFS on a 5,000-node chain hits Python's recursion limit.
- BFS and DFS both run in O(V + E) time on an adjacency list, and BFS uses O(V) space for its queue and visited set.
- BFS reaches nodes in order of distance from the source, so the first time it reaches a node is along a shortest path when every edge costs the same.
- In BFS, a node should be marked seen when it is added to the queue, not when it is removed, or the same node can be queued several times.
- Python allows 1,000 nested calls by default, so recursive DFS on a 5,001-node chain raised RecursionError while an explicit-stack DFS visited all 5,001 nodes.
- DFS with three node states detects a cycle in a directed graph: reaching a node that is still in progress means the path loops back on itself.
- A topological order exists only for a directed graph with no cycles, and DFS produces one by appending each node after its descendants and reversing.
01Graphs as adjacency lists
A graph is nodes (vertices) joined by edges. Interview problems usually give it as a list of edges or a grid, and the first step is to turn it into an adjacency list: for each node, the list of nodes it connects to. Lookup of neighbours is then direct, and memory is O(V + E).
The graph used below has six nodes and is undirected, so each edge is listed in both directions:
g = {'A': ['B', 'C'], 'B': ['A', 'D', 'E'], 'C': ['A', 'F'],
'D': ['B'], 'E': ['B', 'F'], 'F': ['C', 'E']}Both traversals need one extra idea: a seen set. Without it, an undirected graph sends you back and forth along the same edge forever, and any graph with a cycle never stops.
02BFS: level by level with a queue
from collections import deque
def bfs(g, s):
seen, order, dist = {s}, [], {s: 0}
q = deque([s])
while q:
u = q.popleft()
order.append(u)
for v in g[u]:
if v not in seen:
seen.add(v)
dist[v] = dist[u] + 1
q.append(v)
return order, dist
print(bfs(g, 'A'))The output is order A B C D E F and distances A:0, B:1, C:1, D:2, E:2, F:2. A and its neighbours B and C come first, then everything two steps away. Mark a node as seen when you add it to the queue, not when you remove it. Otherwise the same node can be queued several times. The queue gives first-in-first-out order, which is what makes the visit go in widening rings. Time is O(V + E) and memory is O(V).
03Shortest path in an unweighted graph
Because BFS reaches nodes in order of distance, the first time it reaches a node is along a shortest path. To recover the path itself, store each node's parent and walk back from the target.
def path(g, s, t):
prev, q = {s: None}, deque([s])
while q:
u = q.popleft()
if u == t: break
for v in g[u]:
if v not in prev:
prev[v] = u
q.append(v)
if t not in prev: return None
p, x = [], t
while x is not None:
p.append(x); x = prev[x]
return p[::-1]
print(path(g, 'A', 'F'), path(g, 'D', 'F'))The result is ['A', 'C', 'F'] and ['D', 'B', 'E', 'F'], which are 2 and 3 edges long. This only works when every edge costs the same. With different weights the nearest node by edge count is not the nearest by cost, and you need Dijkstra's algorithm, which is BFS with a priority queue instead of a plain queue.
04DFS: go deep, then back up
def dfs(g, s, seen=None, order=None):
if seen is None: seen, order = set(), []
seen.add(s)
order.append(s)
for v in g[s]:
if v not in seen:
dfs(g, v, seen, order)
return order
print(dfs(g, 'A')) # ['A', 'B', 'D', 'E', 'F', 'C']From A it goes to B, then from B to D. D is a dead end, so it backs up to B and continues to E, then F, then back up to A and finally C. Compare this with BFS order A B C D E F. DFS fully explores one branch before starting the next.
DFS does not find shortest paths. In this graph it reaches F through A, B, E, F (three edges) although A to F is two edges via C. Use it when you care about structure rather than distance.
05Recursion limit and the iterative version
Python allows 1,000 nested calls by default. A graph shaped like a long chain exceeds that. I built a chain of 5,001 nodes and the recursive dfs raised RecursionError. The explicit-stack version handled it and visited all 5,001 nodes:
def dfs_iter(g, s):
seen, st, order = set(), [s], []
while st:
u = st.pop()
if u in seen: continue
seen.add(u)
order.append(u)
for v in reversed(g[u]):
if v not in seen: st.append(v)
return orderThe reversed call makes the visit order match the recursive version (A B D E F C on the example). Swap the stack for a queue and you have BFS, which is a useful way to remember how related the two are. In languages with small call stacks, such as C or Java with big inputs, the same advice applies.
06Common uses: islands, topological sort, cycles
Connected components (counting islands in a grid): start a traversal from every unvisited land cell and count how many starts you needed. For the grid ["11000", "11000", "00100", "00011"] that gives 3.
Topological order for a directed acyclic graph, such as course prerequisites: run DFS and append each node after all its descendants, then reverse. With a→b, a→c, b→d, c→d the code below gave ['a', 'c', 'b', 'd'], a valid order, though not the only one.
def topo(dg):
state, out = {}, [] # 1 = in progress, 2 = done
def visit(u):
if state.get(u) == 1: raise ValueError('cycle')
if state.get(u) == 2: return
state[u] = 1
for v in dg[u]: visit(v)
state[u] = 2
out.append(u)
for u in dg: visit(u)
return out[::-1]The same three-state marking detects cycles. Reaching a node that is still in progress means the path loops back on itself. On a→b, b→a this raised the cycle error. A topological order exists only if there is no cycle, so a cycle error also means the prerequisites are impossible.
07Choosing between them
Use BFS for the fewest steps in an unweighted graph, for level-order problems, and for "nearest" questions. Use DFS for exploring every possibility, cycle detection, topological sort, and problems where you build a path as you go and undo it (backtracking).
Both cost O(V + E) time. BFS can hold a whole level in the queue, so on a wide graph its memory can be large. DFS memory is the depth of the graph, which can be small for wide graphs and huge for chains. For a grid with R rows and C columns, V is R times C and each cell has up to four neighbours, so the cost is O(R x C).
08Common interview questions
Q: Which traversal finds the shortest path in an unweighted graph?
A: BFS, because it visits nodes in order of distance from the source.
Q: Why do we need a visited set?
A: To avoid revisiting nodes and looping forever on cycles, and to keep the cost at O(V + E).
Q: Time and space of BFS?
A: O(V + E) time and O(V) space for the queue and visited set.
Q: How do you detect a cycle in a directed graph?
A: DFS with three states. Reaching a node that is currently in progress means a cycle.
Q: When does a topological order exist?
A: Only for directed graphs with no cycles.
Q: What changes when edges have weights?
A: BFS no longer gives shortest paths. Use Dijkstra, or Bellman-Ford if negative weights are allowed.