Uninformed Search: BFS (Breadth-First Search) — Beginner-Friendly Notes

1. What "Uninformed" Means

Search with no hint about where the goal is — only knows states, actions, costs, and goal test. BFS is the most basic uninformed strategy.

Informed (heuristic) search uses an extra hint $h(n)$; uninformed does not.

2. How BFS Works (one line)

Explore layer by layer from start: all nodes at depth 0, then depth 1, then depth 2, ... until goal found.

Queue (FIFO) : [Start] → expand → put children at BACK

Algorithm sketch:

queue = [initial]
while queue not empty:
  node = queue.pop_front()
  if goal_test(node): return path
  for child in successors(node):
    if child not visited: queue.push_back(child)

Requires visited set to avoid looping in graphs.

3. Tiny Trace — Vacuum or Map

• Start A, goal G. BFS expands A → B,C → D,E,F → finds G at shallowest depth first.

4. Properties You Must Remember (for exam table)

Property	Value	Why?
Complete	Yes (if branching $b$ finite)	Will eventually reach every node
Optimal	Yes if step cost = 1 (unweighted)	Finds shallowest goal; not optimal if costs vary (need Uniform Cost Search)
Time	$O(b^d)$ where $d$ = depth of shallowest solution	Expands all nodes up to that depth
Space	$O(b^d)$	Must store frontier — the big drawback

$b$ = branching factor, $d$ = depth.

Beginner intuition: BFS guarantees shortest number of steps but can run out of memory before time — $b=10, d=6$ → 1M nodes.

5. When to Use / Not Use

• Use: small, shallow search; you need optimal in steps; path cost uniform.
• Don't use: large $b$ or deep $d$ (memory explodes); weighted costs (use UCS/A*).

6. BFS vs DFS Preview

• BFS: shallow first → optimal in steps, memory heavy.
• DFS: deep first → memory light, not optimal, can get lost.

7. One-Line Summary to Write in Exam

BFS expands nodes in order of depth using a FIFO queue, is complete and optimal for uniform step costs with $O(b^d)$ time and space, but is memory-intensive for deep searches.

8. Quick Self-Check

1. Why is BFS optimal only when all step costs are equal?
2. What queue type does BFS use and what happens if you use a stack?