Neural Sync Active
↔️ Breadth-First Search (BFS)
Registry Synced
↔️ Breadth-First Search (BFS)
978 words
5 min read
Reading compass
Now · 1. 🎯 Learning Objectives
↔️ Breadth-First Search (BFS)
1. 🎯 Learning Objectives
By the end of this topic, you will be able to:
- Trace the BFS algorithm with full OPEN/CLOSED tables showing state at every step
- Explain why BFS guarantees shortest path (optimality) in unweighted graphs
- Analyze BFS space complexity O(b^d) and why it is exponential
- Compare BFS vs DFS: when each is appropriate
- Identify the first N nodes BFS would inspect given a state space
2. 📋 Prerequisites
| Prerequisite | Course | Why It Matters |
|---|---|---|
| State space | W2 T1 | Understanding state representation |
| Queue data structure | BSCS2002 | BFS uses FIFO queue |
| DFS | W2 T2 | Comparison with BFS |
3. 📖 Core Content
3.1 Intuition: Level-by-Level Exploration
Imagine a search party looking for a lost hiker. BFS is like searching in concentric circles from the last known location — first check all locations 1 km away, then all locations 2 km away, and so on. You systematically expand outward, ensuring you find the closest solution first.
BFS uses a queue (FIFO — First In, First Out) for the OPEN list. It expands all nodes at depth d before expanding any node at depth d+1.
3.2 The BFS Algorithm
textBFS(initial_state, goal_test, move_gen): OPEN = [initial_state] // Queue (FIFO) CLOSED = {} nodePairs = {} while OPEN is not empty: N = dequeue(OPEN) // Remove from front (left side) CLOSED.add(N) if goal_test(N): return reconstruct_path(N, nodePairs) successors = move_gen(N) for each child in successors: if child not in OPEN and child not in CLOSED: enqueue(child, OPEN) // Add to back (right side) nodePairs[child] = N return NO_SOLUTION
3.3 Worked Example: Full BFS Trace
Consider the same graph as before:
(Diagram)
Goal = H. Successors in alphabetical order. BFS trace:
| Step | OPEN (front = left) | CLOSED | N | Successors | Notes |
|---|---|---|---|---|---|
| 0 | [A] | {} | — | — | Initialize |
| 1 | [] | {A} | A | B, C | Not goal. Enqueue B, C |
| 2 | [B, C] | {A} | B | D, E | Not goal. Enqueue D, E |
| 3 | [C, D, E] | {A, B} | C | F, G | Not goal. Enqueue F, G |
| 4 | [D, E, F, G] | {A, B, C} | D | H | Not goal. Enqueue H |
| 5 | [E, F, G, H] | {A, B, C, D} | E | H | E's successor H already in OPEN |
| 6 | [F, G, H] | {A, B, C, D, E} | F | G | F's successor G already in OPEN |
| 7 | [G, H] | {A, B, C, D, E, F} | G | H | G's successor H already in OPEN |
| 8 | [H] | {A, B, C, D, E, F, G} | H | — | H is goal! Path: A-B-D-H |
Order of expansion: A, B, C, D, E, F, G, H Path found: A-B-D-H (length 3) Is this optimal? Yes — BFS finds shortest path (3 edges).
3.4 Worked Example 2: BFS on a Simple Tree
(Diagram)
Goal = F. BFS trace:
| Step | OPEN | CLOSED | N | Successors |
|---|---|---|---|---|
| 0 | [A] | {} | — | — |
| 1 | [] | {A} | A | B, C |
| 2 | [B, C] | {A} | B | D, E |
| 3 | [C, D, E] | {A, B} | C | F, G |
| 4 | [D, E, F, G] | {A, B, C} | D | — |
| 5 | [E, F, G] | {A, B, C, D} | E | — |
| 6 | [F, G] | {A, B, C, D, E} | F | — Goal! |
Order of expansion: A, B, C, D, E, F. Path: A-C-F (length 2). Optimal!
3.5 BFS Properties
| Property | Value |
|---|---|
| Space complexity | O(bd) — exponential |
| Time complexity | O(bd) — exponential |
| Complete? | Yes (if b and d are finite) |
| Optimal? | Yes (shortest path in unweighted graphs) |
| OPEN structure | Queue (FIFO) |
| When to use | Optimality needed, small/dense state spaces |
3.6 Why BFS Space Is Exponential
At depth d, there are bd nodes. BFS must store all of them in OPEN/CLOSED simultaneously because they are all reachable before the goal is found.
Example: b = 10, d = 10 → 10^10 nodes = 10 GB (assuming 1 byte per node — unrealistic). Real memory cost is millions of times higher because each node stores state data, parent pointers, etc.
Compare:
- BFS at depth 20, b=10: ~10^20 nodes. Impossible.
- DFS at depth 20, b=10: ~200 nodes. Trivial.
3.7 BFS vs. DFS: Decision Table
| Criterion | BFS | DFS |
|---|---|---|
| Optimal? | Yes (shortest path) | No |
| Complete? | Yes | Yes (graph-search) |
| Space | O(b^d) — BAD | O(bd) — GOOD |
| Time | O(b^d) | O(b^d) |
| Best when | Short path needed, small state space | Deep solution, limited memory |
3.8 BFS for Configuration Problems
For configuration problems (N-Queens, Sudoku), we still can use BFS, but the OPEN list grows even faster because the branching factor is typically larger (any empty square can be filled). In practice, configuration problems are solved with backtracking (DFS-style) or constraint propagation, not BFS.
4. 📐 Key Formulas / Concepts
| Concept | Value |
|---|---|
| OPEN structure | Queue (FIFO) |
| Time complexity | O(bd) |
| Space complexity | O(bd) |
| Complete? | Yes |
| Optimal? | Yes (shortest path) |
| Max OPEN size | bd (at the deepest level) |
5. ⚠️ Common Pitfalls
Pitfall 1: Forgetting FIFO Order
The mistake: Treating BFS OPEN like a stack and processing the most recent addition first. Correct approach: BFS processes nodes in the order they were added — oldest first, newest last.
Pitfall 2: Assuming BFS is Always Optimal
The mistake: Thinking BFS finds optimal solution in weighted graphs. Correct approach: BFS is optimal only in UNWEIGHTED graphs (where each edge cost is 1). For weighted graphs, use Dijkstra or A*.
Pitfall 3: Underestimating Memory Requirements
The mistake: Running BFS on a problem with b=10, d=100 and expecting reasonable memory. Correct approach: BFS at depth 100 with b=10 would need ~10^100 nodes — physically impossible. Use DFS or heuristic search for deep problems.
6. 📝 Practice Questions
Q1: On graph A-B, A-C, B-D, C-D (square), goal = D. Initial state A. Trace BFS.Answer: Queue: [A]. Pop A, expand -> [B, C]. Pop B, expand -> [C, D]. Pop C, expand -> [D, D2] (C->D already in queue). Pop D -> Goal! Path: A-B-D (or A-C-D, whichever comes first depending on ordering). BFS finds shortest path (2 edges). Q2: If b=4 and goal is at depth 6, how many nodes does BFS store in OPEN at most?Answer: At depth 6, BFS stores all nodes at that depth: 46=4,096 nodes. Total nodes stored (all depths combined) is sum from d=0 to 6 of 4d=(47−1)/(4−1)=16,384−1)/3≈5,461. But at exactly the moment before finding goal, OPEN contains all nodes at depth 6 = 4,096 nodes. Q3: Why can't BFS handle problems like chess (b≈35)?Answer: BFS would need to store 35d nodes. Even at modest depth d=10, that is 3510≈2.8×1015 nodes — trillions of nodes, impossible to store. Join Discord PreviousImplicit vs ExplicitNextDFID (Iterative Deepening)