What is Breadth First Search?

The Breadth First Search (BFS) is an algorithm for traversing or searching tree or graph data structures. It explores all the nodes at the present depth before moving on to the nodes at the next depth level.

Note: It can be implemented using a queue.

The algorithm

Here are the steps for the BFS algorithm:

• Pick a node and enqueue all its adjacent nodes into a queue.

• Dequeue a node from the queue, mark it as visited and enqueue all its adjacent nodes into a queue.

• Repeat this process until the queue is empty or you meet a goal.

The program can be stuck in an infinite loop if a node is revisited and was not marked as visited before. Hence, prevent exploring nodes that are visited by marking them as visited.

Example

We have a directed graph of five nodes with G being the node to be searched. The nodes will be marked as visited using the visited array while adjacent nodes will be added to the queue.

Explanation

Starting from the source node A, we keep exploring down the branches in an ordered fashion i.e. from A to B to C where the level completes. Then we go to the next level and explore D and G.

Time complexity

The time complexity of BFS if the entire tree is traversed is $O(V)$ where V is the number of nodes. In the case of a graph, the time complexity is $O(V + E)$ where V is the number of vertexes and E is the number of edges.