Depth-first search explores as deep as possible before backtracking, using a stack (often the call stack). O(V+E) time. Foundation of cycle detection, topological sort, strongly-connected components, and most maze/backtracking algorithms.
| Best | Average | Worst | Space (Worst) |
|---|---|---|---|
Ω(V+E) |
Θ(V+E) |
O(V+E) |
O(V) |
From the start node, recurse into each unvisited neighbor in turn before moving to the next. With recursion the call stack tracks the path; iteratively, use an explicit stack. Pre-order vs post-order ordering matters: topological sort uses the reverse post-order.
def dfs_recursive(graph, start, visited=None):
if visited is None: visited = set()
visited.add(start)
yield start
for nbr in graph[start]:
if nbr not in visited:
yield from dfs_recursive(graph, nbr, visited)
def dfs_iterative(graph, start):
"""Iterative DFS using an explicit stack — avoids Python recursion limit."""
visited = set()
stack = [start]
while stack:
node = stack.pop()
if node in visited: continue
visited.add(node)
yield node
# reverse so neighbors are popped in original order
for nbr in reversed(graph[node]):
if nbr not in visited:
stack.append(nbr)
def topological_sort(graph):
"""Topological sort via DFS post-order. Assumes a DAG."""
visited, order = set(), []
def visit(n):
if n in visited: return
visited.add(n)
for nbr in graph[n]:
visit(nbr)
order.append(n)
for n in graph:
visit(n)
return order[::-1]
graph = {"A": ["B", "C"], "B": ["D"], "C": ["D"], "D": []}
print(list(dfs_recursive(graph, "A"))) # ['A', 'B', 'D', 'C']
print(topological_sort(graph)) # ['A', 'B', 'C', 'D'] (or 'A', 'C', 'B', 'D')