Python depth-first search
Explore one branch fully before returning to alternatives.
On this page
Recursion, dictionaries, and sets.
- Explore one branch fully before returning to alternatives.
- Predict the sample output and explain the state changes.
- Complete the practice task and check the boundary cases.
The concept
Recursive DFS visits a vertex, then recursively visits each unseen neighbor. The call stack remembers where to resume after a branch finishes.
A seen set makes cyclic graphs terminate. DFS order differs from BFS and does not generally give shortest paths in an unweighted graph.
Code example
def dfs(graph, start):
seen = set()
order = []
def visit(node):
if node in seen:
return
seen.add(node)
order.append(node)
for neighbor in graph.get(node, []):
visit(neighbor)
visit(start)
return order
graph = {"A": ["B", "C"], "B": ["D"], "C": ["D"], "D": ["A"]}
print(dfs(graph, "A"))
assert dfs({}, "Z") == ["Z"]['A', 'B', 'D', 'C']
Follow the code
Open the walkthrough to inspect the example one step at a time.
Show guided walkthrough
def dfs(graph, start): seen = set() order = [] def visit(node): if node in seen: return seen.add(node) order.append(node) for neighbor in graph.get(node, []): visit(neighbor) visit(start) return order graph = {"A": ["B", "C"], "B": ["D"], "C": ["D"], "D": ["A"]}print(dfs(graph, "A"))assert dfs({}, "Z") == ["Z"]Follow the example
Start to inspect the source, values, and output. These prepared steps explain the published sample; grouped loop steps describe multiple iterations.
View the complete dry-run table
| Step / line | What happens | State after step | Output so far |
|---|---|---|---|
| Start recursive traversal at A. | stack = [A] | — | |
| Record A, then follow B. | order = [A] | — | |
| B follows D; D tries A, which is already seen. | stack = [A, B, D], order = [A, B, D] | — | |
| Stop the revisit to A and unwind back to A. | stack = [A, B, D], order = [A, B, D] | — | |
| A's next neighbor C is new; its neighbor D is already seen. | order = [A, B, D, C] | — | |
| Print the completed traversal. | order = [A, B, D, C] | ['A', 'B', 'D', 'C'] |
Behind the scenes
How Python processes this code
Python runs this source through its interpreter. It creates objects for values and resolves names as each statement runs.
Cost and common mistakes
Expected O(V+E) time and O(V) auxiliary space, including recursive frames.
- Deep graphs may exceed Python's recursion limit; an explicit stack avoids recursive depth limits.
- Mark before following neighbors to prevent infinite recursion around cycles.
Try it yourself
Reverse A's neighbor order to [C, B].
Reveal answer and reasoning
The DFS order becomes A, C, D, B for this graph.