Depth-first search & iterative deepening

Go deep first

Depth-first search (DFS) drives down a single path as far as it can before considering any alternative. Where BFS used a FIFO queue, DFS uses a LIFO stack for OPEN: new children are pushed onto the *front* and the next state is taken from the *front* — so the most recently discovered state is expanded next, plunging the search deeper. The only structural change from BFS is *queue → stack*; everything else (OPEN/CLOSED, child generation, cycle detection) is identical.

Equivalently — and this is how the exam expects you to write it — DFS is natural recursion: visit a node, then recurse into each child in turn. The language's own call stack *is* the OPEN stack, and the chain of activation records is the current path. Backtracking happens automatically: when every child of a node fails, the recursive call returns FAIL and control returns to the parent, which tries its next child.

The trade-off against BFS

| | BFS | DFS | |---|---|---| | OPEN | FIFO queue | LIFO stack (or recursion) | | Space | $O(B^n)$ — whole frontier | $O(B \cdot n)$ — one path | | Shortest path? | yes (fewest arcs) | no | | Risk | runs out of memory | can loop forever without a visited set; can dive down an infinite branch |

DFS's *linear* space is its great virtue: for $B = 10$, depth 10, DFS holds about $10 \times 10 = 100$ states versus BFS's $10^{10}$. But DFS gives up the shortest-path guarantee, and without a visited/cycle check it can loop forever on a cyclic graph.

Depth-first iterative deepening (DFID)

DFID gets *both* good properties. Run a depth-limited DFS with limit 1, then 2, then 3, … restarting from scratch each round and discarding state between rounds. Because the goal is found at the smallest depth that contains it, DFID inherits BFS's shortest-path guarantee; because each round is a plain DFS, it keeps DFS's linear space $O(B \cdot n)$. It looks wasteful — shallow levels are regenerated every round — but since the number of nodes grows exponentially with depth, the *deepest* level dominates the total work and the re-generation cost is negligible (Korf, 1987). DFID is the preferred uninformed search when you need both shortest paths and bounded memory.

Worked example — same graph, contrast the order

Reuse the graph from the BFS lesson:

A → B, C    B → D, E    C → F    D → F

From A to F, DFS dives into the *first* child each time: A → B (first child) → D (B's first child) → F. It returns the path A → B → D → F — three arcs, *longer* than the two-arc A → C → F that BFS found, because DFS commits to the first branch rather than sweeping levels. Running depth-limited DFS with growing bounds, DFID first *fails* at depth 0 and 1 (the goal sits below) and *succeeds* at depth 2 — the shallowest depth at which F is reachable, recovering the optimal answer. The runnable cell prints both results.