Overview
Breadth-First Search explores neighbors level by level using a queue.
Analogy
Ripples from a stone: distance 1 first, then distance 2, and so on.
Step-by-step
- Enqueue start node; mark visited.
- While queue not empty:
- Dequeue u; process it.
- Enqueue each unvisited neighbor v of u; mark visited.
- Repeat until queue empty.
Visual
Layered rings from the start; queue holds the current frontier.
Common mistakes
- Marking visited after enqueue, causing duplicates.
- Using a stack (that becomes DFS).
- Not resetting visited between runs.
Practice questions
- Run BFS on a small graph and record order + parent tree.
- Find shortest path in an unweighted graph and reconstruct it.
- Adapt to grid movement (4- or 8-direction).
Space
O(V) for queue + visited
AI Wisdom