Editor

Depth-first search (DFS) in Python

Depth-first search follows one path as deep as it can go, and only when it hits a dead end does it back up and try the next branch. Recursion does the backing up: each call remembers where it was.

The arrow keys step through it. Edit the code to try your own input.

How it works

  1. dfs marks node in visited and adds it to order.
  2. Then it calls itself on the first neighbour that is not visited yet, so the search goes as deep as it can.
  3. A call returns only when its node has no unvisited neighbours left. The caller then tries its own next neighbour: that is backtracking.
  4. The call stack plays the part of a stack of nodes: each frame remembers how far it got through its own neighbour list.

What to watch

  • Watch the call stack grow along A, B, D, then shrink back to B before E is explored.
  • Watch F: E visits it, so when the search backs up to C, F is already in visited.
  • Compare order with breadth-first search on the same graph: A, B, D, E, F, C instead of A, B, C, D, E, F.

The code

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

def dfs(graph, node, visited, order):
    visited.add(node)
    order.append(node)
    for neighbour in graph[node]:
        if neighbour not in visited:
            dfs(graph, neighbour, visited, order)   # go deeper first

visited = set()
order = []
dfs(graph, "A", visited, order)
print(order)
Output
['A', 'B', 'D', 'E', 'F', 'C']

Open it in the editor · Python Program for Depth-First Search on a Graph, explained