Breadth First Search searches breadth-wise in the problem space. Breadth-First search is like traversing a tree where each node is a state which may be a potential candidate for solution.

It expands nodes from the root of the tree and then generates one level of the tree at a time until a solution is found. It is very easily implemented by maintaining a queue of nodes.

Initially the queue contains just the root. In each iteration, node at the head of the queue is removed and then expanded. The generated child nodes are then added to the tail of the queue.

Implementation:

In BFS we use a FIFO queue for the fringe. Because of which the newly inserted nodes in the fringe will automatically be placed after their parents.

Thus, the children nodes, which are deeper than their parents, go to the back of the queue, and old nodes, which are shallower, get expanded first. Following is the algorithm for the same.

Algorithm:

1. Put the root node on a queue.

2. while(queue is not empty)

   a. remove a node from the queue

i) if (node is a goal node)return success;

ii) put all children of node onto the queue; return failure.

Performance Evaluation:

Completeness: It is complete, provided the shallowest goal node is at some finite depth.

Optimality: It is optimal, as it always finds the shallowest solution.

Time complexity: O (bd), number of nodes in the fringe.

Space complexity: O (bd), total number of nodes explored.