Artificial Intelligence : Unit - 2 Part - 3 : Breadth First Search (BFS)

 

UNIT - II

Topic: Breadth First Search (BFS)

---

Introduction

---

What is Breadth First Search?

Breadth First Search (BFS) is an uninformed search strategy that explores the shallowest (nearest) nodes in the search tree before going deeper.

It works level by level, starting from the initial node and moving outward to its neighbors, then their neighbors, and so on.

---

Characteristics of BFS

Feature	Description
Type	Uninformed Search
Search Direction	Level-by-level (horizontal expansion)
Data Structure	Queue (FIFO - First In, First Out)
Completeness	✅ Yes. It guarantees a solution if one exists.
Optimality	✅ Yes (if all steps have equal cost)
Time Complexity	O(b^d) → b = branching factor, d = depth of solution
Space Complexity	O(b^d) → stores all nodes at each level

---

Part C: How BFS Works – Step by Step

1. Start from the initial node and insert it into a queue.
2. Repeat the following steps until the queue is empty:
• Remove the front node from the queue.
• If it is the goal node, return the solution.
• Else, expand the node (generate its child nodes).
• Add the child nodes to the end of the queue.
3. If the queue becomes empty without finding the goal, return failure.

BFS follows these key principles:

1. Level-by-level exploration: Visits all nodes at depth 'd' before moving to depth 'd+1'
2. Queue-based implementation: Uses a First-In-First-Out (FIFO) queue to manage nodes
3. Complete and optimal: For unweighted graphs, it finds the shortest path solution

---

Part D: BFS Algorithm (Pseudo-code)

BFS(initial_node, goal_test):

   create a queue Q

   add initial_node to Q

   create a visited list

   while Q is not empty:

      current_node = Q.dequeue()

      if current_node satisfies goal_test:

          return success (path found)

          mark current_node as visited

      for each neighbor of current_node:

         if neighbor not visited:

          add neighbor to Q

 

The BFS Algorithm Process

1. Initialization:
• Start with the root/initial node
• Create an empty queue and add the root node
• Create a set to track visited nodes
2. Main loop:
• Dequeue the first node from the queue
• Check if it's the goal state (if yes, return solution)
• Otherwise, expand it (generate all successors)
• Enqueue all unvisited successors
• Mark the current node as visited
3. Termination:
• If the queue becomes empty before finding the goal, return failure

Example: Solving a Simple Pathfinding Problem

Let's consider a simple graph representing cities and their connections:

Goal: Find path from A to F using BFS

Step-by-Step Execution:

1. Initialization:
• Queue: [A]
• Visited: {}
2. Level 0 (Depth 0):
• Dequeue A
• Check: A ≠ F (not goal)
• Expand A → [B, C]
• Enqueue B, C
• Visited: {A}
• Queue: [B, C]
3. Level 1 (Depth 1):
• Dequeue B
• Check: B ≠ F
• Expand B → [D, E]
• Enqueue D, E
• Visited: {A, B}
• Queue: [C, D, E]
• Dequeue C
• Check: C ≠ F
• Expand C → [F]
• Enqueue F
• Visited: {A, B, C}
• Queue: [D, E, F]
4. Level 2 (Depth 2):
• Dequeue D
• Check: D ≠ F
• Expand D → [] (no new nodes)
• Visited: {A, B, C, D}
• Queue: [E, F]
• Dequeue E
• Check: E ≠ F
• Expand E → [] (no new nodes)
• Visited: {A, B, C, D, E}
• Queue: [F]
• Dequeue F
• Check: F = F (goal found!)
• Return solution path: A → C → F

 

---

Real-Life Examples of BFS

Scenario	Explanation
Shortest path in maps	BFS helps find the shortest route from one city to another.
Social network search	Finding the shortest connection path between two users (e.g., in Facebook).
Web crawling	Collecting links layer by layer from a website.
Solving puzzles	Like the 8-puzzle or maze, BFS can find the minimum steps to solve.

 

Properties of BFS

1. Completeness: BFS is complete - it will find a solution if one exists
2. Optimality: For unweighted graphs, BFS finds the shortest path (minimum number of edges)
3. Time Complexity: O(b^d), where b is branching factor, d is solution depth
4. Space Complexity: O(b^d) (keeps all nodes in memory)
5. Memory Usage: High, as it stores all expanded nodes

Advantages and Disadvantages

Advantages:

• Guaranteed to find the shortest path in unweighted graphs
• Simple to implement
• Useful when the solution is close to the root

Disadvantages:

• High memory requirements (stores all nodes)
• Inefficient for deep solutions or large branching factors
• Not suitable for weighted graphs (where Dijkstra's would be better)

BFS remains a fundamental algorithm in AI due to its simplicity and guarantee of finding the shortest path in unweighted state spaces, though its memory requirements often make it impractical for large problems.