DFS (Depth-First Search) — Beginner-Friendly Notes

1. How DFS Works (one line)

Go as deep as possible down one path before backtracking: expand deepest node first.

Stack (LIFO): [Start] → expand → put children at FRONT (push)

Sketch:

stack = [initial]
while stack not empty:
  node = stack.pop()  # last in, first out
  if goal_test(node): return path
  for child in successors(node) reversed: stack.push(child)

Needs visited set for graphs to avoid cycles.

2. Trace Contrast with BFS

• BFS: layer by layer (shallow first)
• DFS: dives to depth limit: A → B → D → H ... backtrack when dead end.

3. Properties (exam table — memorise)

Property	Value	Why?
Complete	No (in infinite depth or cycles) / Yes if finite graph + visited + depth bound	Can go forever down infinite branch
Optimal	No	May find deep, costly goal before shallow optimal one
Time	$O(b^m)$ where $m$ = max depth explored	Worst-case explores all
Space	$O(b \cdot m)$ — linear!	Only stores path + frontier — the big advantage

$m$ = maximum depth.

Beginner intuition: DFS is memory-thrifty but risky — like exploring a maze by always turning left; you may find a goal fast or wander deep.

4. When to Use

• Memory is limited, search tree is large.
• You have a depth bound or expect goal is deep.
• You will enhance it with limits → Depth-Limited, Iterative Deepening.

5. Common Mistake

Thinking DFS is always faster — worst-case time is similar to BFS, but space is vastly smaller. Speed depends on where goal sits in tree.

6. One-Line Summary to Write in Exam

DFS uses a LIFO stack to explore deepest nodes first, with $O(b \cdot m)$ space but $O(b^m)$ time, incomplete and non-optimal without a depth bound, but memory-efficient for deep search.

7. Quick Self-Check

1. Why does DFS need a visited set in graphs?
2. Give a state space where DFS beats BFS and vice versa.