DFS Is Not Optimal
Claim
Depth-first search (DFS) does not return a minimum-depth solution in general. The solution it finds depends on the order successors are added to the stack and may be arbitrarily deeper than the shallowest solution (Russell and Norvig 2020).
Proof (by counterexample)
Consider the following search tree with start node \(s\):
\[ s \;\longrightarrow\; \begin{cases} A \;\longrightarrow\; G_2 \quad \text{(goal at depth 2)} \\ G_1 \quad \text{(goal at depth 1)} \end{cases} \]
DFS pushes successors of \(s\) onto a stack. With left-first ordering, \(A\) is pushed before \(G_1\) (so \(A\) sits on top). DFS then pops \(A\), pushes \(G_2\), pops \(G_2\), and returns it as the solution.
DFS returns \(G_2\) at depth 2. The goal \(G_1\) at depth 1 is never examined before the search terminates. \(\square\)
The deficit is structural: a LIFO stack gives priority to depth, not breadth. There is no mechanism to ensure a goal discovered late in the stack ordering is checked before a deeper goal discovered early.
Consequences
The depth of the solution DFS returns can be made arbitrarily large relative to \(d^*\) by placing the optimal goal on the last-explored branch and a suboptimal goal deep in the first-explored branch.
This non-optimality is the primary motivation for iterative deepening search: by running depth-limited searches with increasing limits, IDS recovers the optimality guarantee of BFS while retaining DFS’s linear memory usage. (proof)