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 + b2 +.............. + bd

= O(bd )

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(bd )

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)