Python depth-first search

Explore one branch fully before returning to alternatives.

Python

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"]

Output

['A', 'B', 'D', 'C']

Explanation

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.

Explore the dry run

Guided walkthroughReady

1def dfs(graph, start):

2 seen = set()

3 order = []

4 def visit(node):

5 if node in seen:

6 return

7 seen.add(node)

8 order.append(node)

9 for neighbor in graph.get(node, []):

10 visit(neighbor)

11 visit(start)

12 return order

14graph = {"A": ["B", "C"], "B": ["D"], "C": ["D"], "D": ["A"]}

15print(dfs(graph, "A"))

16assert 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

Prepared trace of the published program. Some rows group repeated iterations.
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']

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.

Python depth-first search

Explanation

Follow the example

Cost and common mistakes

Try it yourself

Further reading