Python DFS Templates (Recursive + Iterative)
DFS visits a graph by going as deep as possible before backtracking. Python lets you write it recursively (concise, but bounded by `sys.getrecursionlimit()`) or iteratively with an explicit stack (uglier, but safe for deep graphs). This entry ships both templates and a third variant that detects cycles in a directed graph using gray / black coloring.
775 views
25
from collections import defaultdict
def dfs_recursive(graph, start):
"""Pre-order DFS via recursion. Returns the visit order."""
visited = set()
order = []
def visit(node):
if node in visited:
return
visited.add(node)
order.append(node)
for nbr in graph[node]:
visit(nbr)
visit(start)
return order
graph = defaultdict(list)
for u, v in [(1, 2), (1, 3), (2, 4), (3, 4), (4, 5)]:
graph[u].append(v)
graph[v].append(u)
print(dfs_recursive(graph, 1)) # e.g. [1, 2, 4, 3, 5]
# Single node, no edges.
solo = defaultdict(list)
solo[7] = []
print(dfs_recursive(solo, 7)) # [7]Recursive DFS reads top-to-bottom: visit the node, mark it, recurse into each neighbor. The closure pattern (visit defined inside dfs_recursive) keeps visited and order out of the public signature. The function is post-order if you append to order AFTER the recursive call instead of before. The only risk is Python's default recursion limit of 1000 frames: deep chains (linked-list-shaped graphs, long paths) crash with RecursionError and you should switch to the iterative version below.
from collections import defaultdict
def dfs_iterative(graph, start):
"""Pre-order DFS via an explicit list-as-stack. Safe for arbitrarily deep graphs."""
visited = set()
order = []
stack = [start]
while stack:
node = stack.pop() # LIFO: last pushed is next visited
if node in visited:
continue
visited.add(node)
order.append(node)
# Push neighbors in reverse so the visit order matches the recursive version.
for nbr in reversed(graph[node]):
if nbr not in visited:
stack.append(nbr)
return order
graph = defaultdict(list)
for u, v in [(1, 2), (1, 3), (2, 4), (3, 4), (4, 5)]:
graph[u].append(v)
graph[v].append(u)
print(dfs_iterative(graph, 1)) # e.g. [1, 2, 4, 3, 5]
# Million-deep linear chain: recursion would hit RecursionError, this works.
chain = defaultdict(list)
for i in range(2000):
chain[i].append(i + 1)
result = dfs_iterative(chain, 0)
print(len(result), result[:3], '...', result[-3:])
# 2001 [0, 1, 2] ... [1998, 1999, 2000]Iterative DFS replaces the call stack with an explicit Python list. list.pop() is O(1) from the end, which gives LIFO semantics, the same as recursion. To match the recursive visit order exactly, push neighbors in reverse so the first neighbor lands on top of the stack and is visited next. The iterative version handles arbitrarily deep graphs without bumping sys.setrecursionlimit, which is the right move for production code that might process untrusted input. The check if node in visited: continue after the pop matters: a node can be pushed twice before either copy is processed.
from collections import defaultdict
def has_cycle(graph):
"""True if the directed graph contains any cycle."""
WHITE, GRAY, BLACK = 0, 1, 2
color = defaultdict(lambda: WHITE)
def dfs(node):
color[node] = GRAY # entering the node
for nbr in graph[node]:
if color[nbr] == GRAY:
return True # back-edge: cycle!
if color[nbr] == WHITE and dfs(nbr):
return True
color[node] = BLACK # done with this subtree
return False
for node in list(graph):
if color[node] == WHITE and dfs(node):
return True
return False
acyclic = defaultdict(list)
for u, v in [(1, 2), (2, 3), (1, 3)]:
acyclic[u].append(v)
print(has_cycle(acyclic)) # False
cyclic = defaultdict(list)
for u, v in [(1, 2), (2, 3), (3, 1)]:
cyclic[u].append(v)
print(has_cycle(cyclic)) # True
self_loop = defaultdict(list)
self_loop[1].append(1)
print(has_cycle(self_loop)) # TrueCycle detection in a directed graph needs three colors, not two. White = unseen, gray = currently on the recursion stack, black = fully processed. A back-edge (the only kind of edge that creates a cycle in a DFS tree) is exactly an edge from gray to gray. A two-color visited set is wrong because it cannot tell the difference between 'I've seen this node before in another branch' (cross-edge, not a cycle) and 'I'm currently inside this node' (back-edge, cycle). The same coloring drives topological sort: emit a node when it turns black, then reverse the list.