**Breadth-first search **is a simple strategy in which the root node is expanded first, then all the successors of the root node are expanded next, then their successors, and so on. In general, all the nodes are expanded at a given depth in the search tree before any nodes at the next level are expanded.

Breadth-firsts each can be implemented by calling **TREE- SEARCH** with an empty fringe that is a first-in-first-out (FIFO) queue, assuring that the nodes that are visited first will be expanded first.

In other words, calling **TREE-SEARCH (Problem, FIFO- QUEUE ()) **results in a breadth-first search. The FIFO queue puts all newly generated successors at the end of the queue, which means that shallow nodes are expanded before deeper nodes.

### Breadth first search trees after node expansions

**Example: Route finding problem**

*Task: *Find a, path from. S to G using BFS

The path in the 2nd depth level is selected, (i.e) SBG{or) SCG.

### Algorithm of Breadth First Search :

**function ***BFS{problem)*returns a solution or failure

**return **TREE-SEARCH*(problem,*FIFO-QUEUE( ))

### Time and space complexity:

**Example:**

#### Time complexity

= 1 +b *+ b ^{2} +.............. + b^{d}*

*= O(b^{d} )*

The **space complexity **is same as time complexity because all the leaf nodes of the tree must be maintained in memory at the same time *= O(b^{d} )*

##### Completeness: Yes

*Optimality**: *Yes, provided the path cost is a non decreasing function of the depth of the node

** Advantage:** Guaranteed to find the single solution at the shallowest depth level

** Disadvantage: **Suitable for only smallest instances problem (i.e.) (number of levels

to be mininimum (or) branching factor to be minimum)