Breadth-First Search (BFS)

Understanding graph traversal and shortest path search (used in the a-maze-ing project)

---

Table of Contents

1. What is BFS?
2. Graph Traversal
3. Queue Concept
4. Why BFS uses deque
5. Layer-by-Layer Exploration
6. Visual Example
7. BFS Logic
8. Visited Nodes
9. Parent Tracking
10. Path Reconstruction
11. Complexity
12. BFS vs Dijkstra
13. Fly-in Connection
14. Mental Model

---

1️⃣ What is BFS?

BFS means:

Breadth-First Search

It is an algorithm used to:

• traverse graphs
• explore neighbors
• find shortest paths
• avoid infinite loops

---

BFS explores:

layer by layer

NOT:

deep first

---

2️⃣ Graph Traversal

Imagine this graph:

        start
       /  |  \
      A   B   C
     /         \
    D           goal

BFS explores:

start
↓
A B C
↓
D goal

It explores all neighbors before going deeper.

---

3️⃣ Queue Concept

BFS uses:

FIFO Queue

FIFO means:

First In
First Out

---

Example

ADD A
ADD B
ADD C

Queue:

[A, B, C]

Remove:

A

because:

A entered first

---

4️⃣ Why BFS uses deque

Python provides:

from collections import deque

deque means:

double-ended queue

---

Useful Operations

append()
popleft()

---

Example

from collections import deque

queue = deque()

queue.append("A")
queue.append("B")
queue.append("C")

print(queue.popleft())

Output:

A

---

5️⃣ Layer-by-Layer Exploration

BFS explores nodes in waves.

---

Visual Example

LEVEL 0:
start

LEVEL 1:
A B C

LEVEL 2:
D goal

BFS always explores:

closest nodes first

---

6️⃣ Visual Simulation

Imagine water spreading:

start
  ↓
A B C
  ↓
D goal

BFS spreads equally in all directions.

---

7️⃣ BFS Logic

Core Idea

Explore neighbors first.

---

Pseudo Code

CREATE queue
CREATE visited set
CREATE parent dictionary

ADD start zone to queue
MARK start as visited

WHILE queue not empty:

    current = queue.pop_left()

    IF current == goal:
        reconstruct path
        RETURN path

    FOR each connected zone:

        IF not visited:

            mark visited
            save parent
            add to queue

---

8️⃣ Visited Nodes

BFS MUST track visited nodes.

Why?

Because graphs may contain loops.

---

Example

A -> B
↑    ↓
D <- C

Without visited tracking:

infinite loop

---

Visited Set

Example:

visited = {
    "start",
    "A",
    "B"
}

---

9️⃣ Parent Tracking

BFS usually stores:

where each node came from

---

Example

{
    "A": "start",
    "goal": "C"
}

This allows path reconstruction later.

---

🔟 Path Reconstruction

Once BFS reaches the goal:

go backwards using parents

---

Example

goal
 ↑
 C
 ↑
 start

Reverse result:

start -> C -> goal

---

1️⃣1️⃣ Complexity

BFS complexity is usually:

O(V + E)

Where:

V = vertices (zones)
E = edges (connections)

---

1️⃣2️⃣ BFS vs Dijkstra

BFS

Good for:

• unweighted graphs
• same movement costs
• shortest path in number of steps

---

Dijkstra

Good for:

• weighted graphs
• movement costs
• cheapest total route

---

Example

BFS thinks:

fewest movements

Dijkstra thinks:

lowest total cost

---

1️⃣3️⃣ Fly-in Connection

Fly-in uses:

normal      = 1
priority    = 1
restricted  = 2
blocked     = impossible

This means:

not all paths cost the same

So:

BFS is useful to learn graph traversal

BUT:

Dijkstra fits Fly-in better

---

1️⃣4️⃣ Mental Model

Think of BFS like:

water spreading equally

or:

exploring closest rooms first

---

Final Mental Image

BFS always asks:

"What is the closest unexplored node?"

NOT:

"What is the cheapest node?"

That is the BIG difference between:

BFS
vs
Dijkstra