Breadth First Search Algorithm
Breadth first search is belongs to a family of search algorithm named Uninformed Search, also called Blind Search. The term means that the strategies have no additional information about states beyond that provided in the problem definition. All these algorithm can do is generate successors and distinguish a goal state from nongoal state.
Breadth First Search Algorithm
BreadthFirst Search is a simple search strategy in which the root node is expanded first, then all the successor 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 First Search is an instance of general graphsearch algorithm discussed in Searching For Solutions, in which the shallowest unexpanded node is chosen for expansion. This is achieved very simply by using a FIFO queue for the frontier. Thus, new nodes (which are always deeper than their parent) go to the back of the queue, and old nodes, which are shallower than the new nodes, get expanded first. There is slight tweak on the general graph search algorithm, which is:
The goal test is applied to each node when it is generated rather than when it is selected for expansion.Since, general template for graph search, discards any new path to a state already in the frontier or explored set; it is easy to see that any such path must be at least as deep as the one already found. Thus, breadth first search always have the shallowest path to every node on the frontier.
function BREADTHFIRST_SEARCH(problem) return a solution or failure node < A node with {STATE = problem.INITIALSTATE and PATHCOST = 0} if problem.GOALTEST(node.STATE): return solution(node) frontier < A FIFO Queue with node as the only element explored < An empty set loop: if EMPTY(frontier): return failure node < POP(frontier) //choose the shallowest node in frontier add node.STATE to explored for each action in problem.ACTIONS(node.STATE): child < CHILDNODE(problem, node, action) if child.STATE is not in explored or frontier: if problem.GOALTEST(child.STATE): return SOLUTION(child) frontier < INSERT(child, frontier)
Performance of Breadth First Search Algorithm

Completeness
BFS algorithm is complete. If the shallowest goal node is at some finite depth \(d\), breadth first search will eventually find it after generating all the shallower node, provided the branching factor \(b\) is finite.

Optimality
As soon as goal node is generated, we know that it is the shallowest goal node because all shallower node must have been generated already and failed the goal test. Now the shallowest goal node is not necessarily the optimal one. Technically, BFS is optimal, only if the path cost is a non decreasing function of the depth of the node. The most common such scenario is that all action have the same cost.

Time Complexity
Imagine searching a uniform tree where every state has \(b\) successors. The root of the search tree generates \(b\) nodes at the first level, each of which generates \(b\) more nodes, for a total of \(b^2\) at the second level. Each of these generates \(b\) more nodes, yielding \(b\) nodes at the third level, and so on. Now suppose that the solution is at depth \(d\). In the worst case, it is the last node generated at the last level. Then the total number of nodes generated is
$$b + b^2 + b^3+ … +b^d = \mathcal O(b^d)$$
If in above mention algorithm we apply the goal test to nodes when selected for expansion, rather than when generated, then time complexity is \( \mathcal O(b^{d+1})\) because, the whole layer of nodes at depth d would expanded before the goal was detected.

Space Complexity
For any kind of graph search, which stores every expanded node in the explored set, the space complexity is always within a factor of \(b\) of the time complexity. For BFS, every node generated remains in memory. There will be \(\mathcal O(b^{d1})\) nodes in the explored set and \( \mathcal O(b^d)\) nodes in frontier. So the space complexity is \(\mathcal O(b^d)\), i.e., it is dominated by the size of the frontier.
Why exponential time complexity is scary?
Let us compute the time and space requirement for various values of depth \(d\). For this consider, branching factor \(b = 10\). Suppose, \(1\) Million nodes can be generated per second and a node requires 1000 bytes of storage. Two lesson can be learned from the above figure:
 The memory requirements are a bigger problem for breadth first search than is the execution time. One might wait 13 days for the solution to an important problem with search depth 12, but no personal computer has the peta byte of memory it would take.
 Time is still a major factor. If your problem has a solution at depth 16 then it will take 350 years for breadth first search to find it.
In general, exponential time complexity search problems can not be solved by uninformed methods except small instances.
This article is contributed by Ram Kripal. If you like eLgo Academy and would like to contribute, you can mail your article to admin@elgoacademy.org. See your article appearing on the eLgo Academy page and help others. Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.