BFS Search Algorithm in Artificial Intelligence (AI)

BREADTH FIRST SEARCH|UNINFORMED SEARCH |BLIND SEARCH

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-first search is an instance of the general graph-search algorithm 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 parents) go to the back of the queue, and old nodes, which are shallower than the new nodes, get expanded first.

There is one slight tweak on the general graph-search algorithm, which is that the goal test is applied to each node when it is generated rather than when it is selected for expansion.

Note also that the algorithm, following the 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 has the shallowest path to every node on the frontier.

1. If you can easily see that it is complete — if the shallowest goal node is at some finite depth d
2. breadth-first search will eventually find it after generating all shallower nodes (provided the branching factor b is finite).
3. As soon as a goal node is generated, we know it is the shallowest goal node is it because all shallower nodes must have been generated already and failed the goal test.
4. Note:- the shallowest goal node is not necessarily the optimal one.

Procedure of BFS Algorithm

• It uses a queue data structure (FIFO)
• Any node in the graph is marked as the root to begin traversal.
• It keeps dropping the node in the graph as it traverses through all nodes.
• The algorithm visits the adjacent unvisited nodes and keeps them inserting into the queue.
• In case no adjacent vertex is found, it removes the previous vertex from the queue.
• The BFS algorithm iterates until all the vertices are visited or traversed and marked as completed.
• The algorithm doesn’t cause any loops during traversal of data from any node.

Summary

The BFS is an efficient algorithm with the complexity of O(V + E), and its graph traversal consists of a smaller number of iterations in the shortest possible time and doesn’t get stuck in an infinite loop. The algorithm is used in multiple real-life applications such as web crawlers, P2P networks because of its robust nature.