Depth-First Search

Depth-first search follows one path as deep as it can go, then backs up to the last place with an unexplored option — using recursion (the call stack).

Start at A

A
B
C
D
E
F

Call stack (bottom → top)

empty

Visit order: —

  • Current
  • On the call stack
  • Visited
  • Edge being checked

DFS goes as deep as it can along one path before backing up. The call stack remembers the way back.

Step 1 / 32
Visited
0
Stack depth
0
dfs(node):
  mark node visited
  for each neighbour of node:
    if not visited: dfs(neighbour)
  // all neighbours done: back up
Start at

What's happening?

  1. Visit the start node and mark it visited.
  2. Go to its first unvisited neighbour and repeat from there — deeper and deeper.
  3. When a node has no unvisited neighbours, back up one level and try the next option.

Complexity

Time
O(V + E) — every node and edge once
Space
O(V) for the call stack in the worst case

Where you'll meet it

Maze and puzzle solving (backtracking), detecting cycles, topological sort for build systems and course prerequisites, and finding connected components.

Common mistake

Recursing on very deep graphs without limit — the call stack overflows. Use an explicit stack for huge graphs.

FAQ

Does DFS find the shortest path?

No. It finds a path, not necessarily the shortest — use BFS (equal costs) or Dijkstra (weights).

Recursive or iterative DFS?

Both work. Recursion is shorter to write; an explicit stack avoids stack-overflow on deep graphs.

Why did DFS and BFS visit the same order from A here?

On this graph they happen to — but look at the trees they build: BFS spreads out from A, DFS makes one long chain.