Depth-First Search (DFS)

The impetuous search — dive deep, backtrack late. Linear space but no shortest-path guarantee

The Simplest Explanation

DFS is the impetuous tourist. It sees a street and immediately walks down it, as far as it can go. Only when it hits a dead end does it back up one step and try the next street.

The entire algorithm is the general generate-and-test loop with one line deciding its personality:

Add new nodes at the head of Open → Open behaves like a stack (LIFO) → always explore the newest node first.

Remember This

DFS = add to head = LIFO = go deep first. Everything else about DFS follows from this single choice.

The Algorithm

Open starts as [(S, nil)], Closed as []. Repeat while Open is not empty:

Pick the first pair (n, parent) from Open
If GoalTest(n) passes → trace parents and return the path
Move n to Closed
neighbors = RemoveSeen(MoveGen(n), Closed)
newPairs = MakePairs(neighbors, n)
Prepend newPairs to Open (newPairs ++ Open)

Step 6 is the only difference from BFS.

In this snapshot DFS has visited S → A → D. The frontier nodes (E, B, C) wait on Open while DFS keeps diving. It returns to them only after the deep branch is exhausted.

Interactive Trace

Watch DFS run on a graph where the goal hides behind two routes — a long one through A-C and a short one through D:

Blind Search TraceStep 0 / 4

Current

On Open (frontier)

Closed (visited)

Path to Goal

Initialize: Open = [(S, nil)], Closed = []. S is the start state.

Open (stack — add at head)

[(S, ·)]

Closed

[]

Key Observations

DFS dives: from S it commits to A, then C, never glancing at D until forced.
It finds a longer path: S → A → C → G (length 3), even though S → D → G (length 2) exists. DFS has no sense of direction.
Open stays thin: at every moment Open holds just a handful of nodes — one or two per level of depth.

Analysis

Assume constant branching factor $b$ and goal at depth $d$ .

Time Complexity

Scenario	Nodes inspected
Best case (goal on leftmost path)	$O(d)$
Worst case (goal on rightmost path)	$O(b^d)$
Average	$\approx O(b^{d/2})$

On average DFS inspects about half the tree's depth before hitting the goal — if you're lucky enough for the goal to be on an early-explored branch.

Space Complexity — DFS's Superpower

At each level, DFS generates $b$ children, picks one, and parks the other $b-1$ on Open. Over depth $d$ :

$|\text{Open}| = (b-1)\cdot d = O(bd) \quad \text{— linear!}$

BFS by contrast holds $O(b^d)$ nodes on Open. For large problems, BFS runs out of memory long before time becomes the issue; DFS never does.

Solution Quality and Completeness

Property	Value
Shortest path guaranteed?	No — may find a longer path down an early branch
Complete on finite spaces?	Yes — will eventually explore everything
Complete on infinite spaces?	No — can dive forever down one infinite branch
Optimal?	No

The Cycle Danger

Without pruning, DFS can loop forever: S → A → S → A → ... Open never empties. This is why loop checking matters more for DFS than for any other algorithm:

With Closed list: safe, each node expanded once
Without any pruning: infinite loops on cyclic spaces

When NOT to Use DFS

Never use plain DFS when (a) the space has cycles and you have no memory for a Closed list, or (b) you need the shortest path. Use DFID instead — it fixes both problems for only ~11% extra work.

QuizWhat is the ONLY line that differs between the DFS and BFS pseudocode?

QuizDFS inspects how many nodes in the worst case (branching factor b, goal at depth d)?

QuizWhy does DFS use only O(bd) space?