📘 Breadth-First Search (BFS)

 

Breadth-First Search (BFS)

🔷 1.Definition:
Breadth-First Search is a systematic uninformed search strategy where:

• The root node is expanded first.
  
  

• Then all its child nodes are expanded.
  
  

• Then their children are expanded, level by level.

✔ Key property:
BFS explores all nodes at depth d before exploring nodes at depth d+1.

---

🔷 2. When to use BFS?

• All actions have the same cost → guarantees finding the shortest solution (minimum nu

• mber of actions).

✅ Example problems:

• Finding the shortest route in an unweighted graph.

---

🔷 3. Example:

City route tree example:

         A

        /   \

      B       C

     / \     / \

    D   E   F   G

✔ Start from A (root).

✔ Order of exploration:
A → B, C → D, E, F, G

✔ Explanation:

• First expand A.
  
  

• Then expand its children B and C.
  
  

• Next expand D, E, F, G.
  
  

✅ Result: Finds shortest path first.

---

🔷 4. Implementation Insights

✔ Uses a FIFO (First-In-First-Out) queue to store the frontier.

Frontier Queue (FIFO):

[Front] A → B → C → D → E → F → G [Rear]

Step by Step:

1. Start with root node A.

   Queue: [A]

2. Expand A. Add its children B, C to queue.

   Queue: [B, C]

3. Expand B. Add its children D, E.

   Queue: [C, D, E]

4. Expand C. Add its children F, G.

   Queue: [D, E, F, G]

5. Expand D. (No children)

   Queue: [E, F, G]

6. Expand E. (No children)

   Queue: [F, G]

7. Expand F. (No children)

   Queue: [G]

8. Expand G. (No children)

   Queue: []

✔️ **Order of Expansion:** A → B → C → D → E → F → G

✔ Early Goal Test:
Checks if a node is the goal as soon as it is generated for efficiency.

Example :

Goal: E

BFS with Early Goal Test

Step by Step:

1. Start with node A.

   - Generate children B, C.

   - Check B: Is B the goal? ❌

   - Check C: Is C the goal? ❌

   Queue: [B, C]

2. Expand B.

   - Generate children D, E.

   - Check D: Is D the goal? ❌

   - Check E: Is E the goal? ✅ ✔️ **Goal found immediately upon generation.**

   Queue: [C, D, E]

✔️ **Explanation:**

- **Early Goal Test:** Checks goal condition **immediately when a node is generated** (during expansion), **before adding it to the queue**.

- Saves time by **stopping the search early** as soon as the goal is found, without expanding unnecessary nodes.

---

🔷 5. Key Properties of Breadth-First Search (BFS)

Property	Explanation
✅ Completeness	✔ Complete. It always finds a solution if one exists because it explores all nodes level by level.
✅ Optimality	✔ Optimal (Cost-Optimal) when all actions have the same cost. It guarantees the shortest path (minimum number of steps).
✅Time Complexity	O(b^d) where b = branching factor, d = depth of the shallowest solution. Time grows exponentially with depth.
✅Space Complexity	O(b^d). Needs to store all nodes in the frontier at each level, leading to high memory usage.

BFS Time Complexity Formula :O(b^d)

✔️ Branching factor (b):

• Each node has at most 2 children, so b = 2.

✔️ Depth of shallowest goal (d):

• If the goal is at level 2, e.g., nodes D, E, F, G, then d = 2 (counting root as level 0).

✅ Calculation here:

• At depth 0: b⁰ = 1 node (A)
  
  

• At depth 1: b¹ = 2 nodes (B, C)
  
  

• At depth 2: b² = 4 nodes (D, E, F, G)
  
  

✔ Total nodes generated = 1 + 2 + 4 = 7 nodes

---

⚠ Why is this problematic?

Memory grows exponentially with depth.

✅ Example Calculation (Real-World Scenario):

• Branching factor (b): 10
  
  

• Depth (d): 10
  
  

✔ Nodes generated:
1 + 10 + 100 + … + 10^10 ≈ O(10^10)

✔ Time:
At 1 million nodes/second, takes < 3 hours.

✔ Memory:
Each node = 1 KB → total 10 Terabytes RAM needed.

⚠ At depth d=14, even with infinite RAM, execution time = 3.5 years!

---

How BFS Enhances Search Efficiency:

1. Systematic Exploration:

   • BFS expands all nodes level-wise. This ensures no node is missed and the shallowest solution is found first.

2. Shortest Path Guarantee:

   • If each move has the same cost, BFS guarantees to find the least number of steps to the goal.

3. Useful for Unweighted Problems:

   • Efficient in unweighted graphs or trees (e.g., puzzles, mazes) where shortest path is needed.

4. Prevents Infinite Loops:

   • With proper use of a visited set, it avoids revisiting nodes, making it suitable even for cyclic graphs.

---

BFS is a complete and optimal search strategy for many problem-solving applications. Its level-wise approach helps ensure early detection of solutions and a systematic traversal of the problem space.

Question :

1. Apply the Breadth-First Search (BFS) algorithm to solve a tree traversal problem.Given a start node and goal node in a tree, show step-by-step how BFS is applied and explain how it ensures efficient search.