What is Breath-First Search Algorithm?

Breath-First search involves traversing a binary search tree one level at a time. Starting with the root node, proceeding through neighboring nodes moving towards the next level of nodes. As this process can be performed utilizing FIFO (First in First Out) data structure. This strategy gives the shortest path to the solution. BFS assigns two values to each node: distance and predecessor.

• A distance is calculated by giving the minimum number of edges in any path from the source node to node “v”.
• The predecessor node of “v” along with some shortest path from the source node. The source node's predecessor is some special value, such as null, indicating that it has no predecessor.

If there is no path from the source node to node “v”, then v's distance is infinite, and it is assumed that predecessor has the same special value as the source's predecessor.