Iterative-deepening DFS

O(b^d)

Iterative-deepening DFS (IDDFS) combines the best of BFS and DFS. It runs a depth-limited DFS with limit 0, then 1, then 2, and so on, restarting from scratch each time. Each round only uses memory proportional to the current depth (a single path), like DFS — yet because the limit grows one level at a time, nodes are first reached at their shallowest depth, like BFS. The apparent waste of re-exploring shallow nodes is small: the deepest level dominates the work, so the total is the same order as a single DFS. It's the basis of IDA* and depth-limited game-tree search, used when the graph is huge or infinite and memory is tight.

Click empty space = vertex · click two vertices = edge · drag = moveStart: A
Input graph
Stack
Press ▶ to run
Edit the input and press Play

How it works

  1. Run a depth-limited DFS with the limit set to 0 (just the start).
  2. Increase the limit by one and run the whole DFS again from the start.
  3. Each round reaches one level deeper; shallow nodes are re-explored.
  4. Stop once a deeper limit turns up no new nodes — everything is found.

Pseudocode

1IDDFS(graph, start):                # O(b^d)2  for limit = 0, 1, 2, …:           # grow the depth cap3    depthLimitedDFS(start, limit)    # re-explore from scratch4    if no deeper node appeared: stop56depthLimitedDFS(node, limit):7  visit(node)8  if depth(node) < limit:9    recurse into unvisited neighbours