### Explain Breadth-first search (BFS) with an example. List down the advantages and disadvantages of BFS – Artificial Intelligence

### Breadth-first search (BFS)

Breadth-First –Search is an uninformed search technique. Consider the state space of a problem that takes the form of a tree. Now, if we search the goal along with each breadth of the tree, starting from the root and continuing up to the largest depth, we call it breadth-first search.

**Algorithm: Breadth-First Search**

1. Create a variable called NODE-LIST and set it to the initial state. 2. Until a goal state is found or NODE-LIST is empty: a)Remove the first element from NODE-LIST and call it E. If NODE-LIST was empty. quit. b)For each way that each rule can match the state described in E do: i) Apply the rule to generate a new state, ii) If the new state is a goal state. quit and return this state. iii) Otherwise, add the new state to the end of NODE-LIST

### Breadth-First Search – Example

Let us consider the following tree. Here node **‘A’** is the source or start or initial node and node **‘G’** is the goal node.

Step 1: Initially NODE-LIST contains only one node corresponding to the source state A.

NODE-LIST: A

Step 2: Node A is removed from NODE-LIST. The node is expanded, and its children B and C are generated. They are placed at the back of NODE-LIST.

NODE-LIST: B C

Step 3: Node B is removed from NODE-LIST and is expanded. Its children D, E are generated and put at the back of NODE-LIST.

NODE-LIST: C D E

Step 4: Node C is removed from NODE-LIST and is expanded. Its children D and G are added to the back of NODE-LIST.

NODE-LIST: D E D G

Step 5: Node D is removed from NODE-LIST. Its children C and F are generated and added to the back of NODE-LIST.

NODE-LIST: E D G C F

Step 6: Node E is removed from NODE-LIST. It has no children.

NODE-LIST: D G C F

Step 7: D is expanded; B and F are put in OPEN.

NODE-LIST: G C F B F

Step 8: G is selected for expansion. It is found to be a goal node. So the algorithm returns the path A C G by following the parent pointers of the node corresponding to G. The algorithm terminates.

**Advantages of Breadth-first search are:**

One of the simplest search strategies.

Complete. If there is a solution, BFS is guaranteed to find it.

If there are multiple solutions, then a minimal solution will be found

The algorithm is optimal (i.e., admissible) if all operators have the same cost. Otherwise, breadth-first search finds a solution with the shortest path length.

Finds the path of minimal length to the goal.

**Disadvantages of Breadth-first search are:**

Requires the generation and storage of a tree whose size is exponential to the depth of the shallowest goal node.

The breadth-first search algorithm cannot be effectively used unless the search space is quite small.

### Summary

This article discusses breadth-first search (BFS) with an example. Also, advantages and disadvantages of BFS – Artificial Intelligence. If you like the material share it with your friends. Like the **Facebook page** for regular updates and **YouTube channel** for video tutorials.