Depth-First Search

search

Definition

Depth-First Search

Depth-first search is about expanding the deepest unexpanded node. The frontier is a LIFO queue, i.e., put successors at front.

Properties

Completeness

No, DFS is not generally complete. It fails in infinite-depth spaces and state spaces with loops (free-like search)

It can be modified to avoid repeated state along path (explored set, frontier). Then, DFS is complete in finite spaces.

Time Complexity

The time complexity is $O(b^m)$, where $m$ is the maximum depth of the state space. DFS is very expensive if $m$ is much larger than $d$, but if solutions are dense, it might be much faster than BFS.

Space Complexity

The space complexity is $O(bm)$ and thus linear.

Optimality

DFS is not generally optimal. But there ‘s a variant with backtracking (keep one successor node at a time)’, which is optimal.