Depth-first search visualization

Depth-first search (DFS) is a graph traversal algorithm that follows a path as deep as it can before backtracking. From the current node it moves to an unvisited neighbor and keeps going. When a node has no unvisited neighbors left, it is finished and the search steps back to the node that called it.

How it works

1. Mark the start node as visited.
2. For each neighbor of the current node, in order: if it is not visited, visit it by repeating these steps from that neighbor.
3. When every neighbor has been handled, the node is finished and control returns to the node that reached it.

The visited flag

Graphs can contain cycles, so DFS marks each node as visited the moment it enters it. Without that mark, a cycle would send the recursion round and round forever.

A worked example of depth-first search

Use the Road map graph with start node A and neighbors in alphabetical order. The edges are A-B, A-C, C-B, B-D, C-E, D-F, E-F.

1. Visit A. Call stack: A.
2. Visit B. Call stack: A, B.
3. Visit C. Call stack: A, B, C.
4. Visit E. Call stack: A, B, C, E.
5. Visit F. Call stack: A, B, C, E, F.
6. Visit D. Call stack: A, B, C, E, F, D.

After F, node D is the last new node. Then the calls finish in the order D, F, E, C, B, A, each one returning to the call below it on the stack. DFS made 14 visited-checks. The visiting order is A, B, C, E, F, D. Compare it with breadth-first search on the same graph: D is only 2 edges from A (through B), but DFS reaches it last, at the end of a path that is 5 edges long.

Depth-first search pseudocode

G is the graph as adjacency lists, s is the start node, and neighbors are taken in increasing node order, as in the code of this lesson. visited and order are shared by all calls.

DFS(G, s)
1  for each node v in G
2      visited[v] = false
3  order = empty list
4  VISIT(G, s)
5  return order

VISIT(G, u)
1  visited[u] = true
2  append u to order
3  for each neighbor v of u
4      if not visited[v]
5          VISIT(G, v)

Line 1 of VISIT marks the node before any recursive call, which is what stops a cycle from looping. When the for loop ends, the call returns and the caller continues with its next neighbor.

Time and space complexity

Each node is entered once and each edge is checked a constant number of times. With V nodes and E edges as adjacency lists:

• Time: O(V + E), because every node is visited once and every adjacency list is scanned once.
• Space: O(V), for the visited table plus the recursion stack, which can be as deep as the longest path: up to V calls.

When to use it, and when not to

• Use it to check whether one node can reach another, and to find connected groups.
• Use it to detect cycles and to order tasks that depend on each other (topological order).
• Use it to explore every possibility along one path first, as in mazes and puzzles.
• Do not use it to find the shortest path. DFS finds a path, and which one depends on the order of the neighbors: this lesson takes them alphabetically. For the fewest edges, use breadth-first search.

Where depth-first search is used

• Ordering tasks with dependencies. A topological order lists every task after the tasks it depends on. Listing the nodes in the reverse of the order in which DFS finishes them gives one (Cormen et al., chapter 20). Build tools and package installers need exactly this order.
• Finding cycles. If DFS reaches a node that is still on the call stack, and not just the one it came from, the path on the stack from that node to the current one closes a loop. This is how a tool can report circular imports between modules, or a deadlock in a graph of processes waiting for each other.
• Backtracking in puzzles. A Sudoku or N-queens solver tries a choice, goes deeper, and undoes the choice at a dead end. That is a depth-first search over the tree of possible choices, and the call stack remembers the choices made so far.

Related algorithms and variations

An iterative version replaces the recursion with an explicit stack, which avoids the call-stack overflow on very deep graphs. Recording a node when it is entered gives a preorder, and recording it when it finishes gives a postorder, which is the one topological sorting uses. Tarjan's strongly connected components algorithm (1972) is a single depth-first search with extra bookkeeping. Iterative deepening runs depth-limited searches with a growing limit, so it uses the memory of DFS and still finds the shallowest answer, as breadth-first search does.

The usual comparison is with breadth-first search (BFS vs DFS). For weighted graphs, see Dijkstra's algorithm (DFS vs Dijkstra).