BFS : Breadth-first search algorithm

BFS or Breadth-first search algorithm for a graph with an example. In the problem, you will see a tree is given. There will be a goal node also. 

Learn the DFS algorithm.


You have to go to the goal node from the root node by using a Breadth-first search. The node in level 0(Before that level there is no edge) is called the root node.

Breadth-first search;

Rules to follow:

  • See the given goal node
  • Leveling
  • Start Visiting from the root node and then left to right from each level
  • If you find the goal node then stop searching


Goal node = I
Breadth-first search

Here A is the root node. Also, it is in level 0 because there is no edge before the level
In the next level, there is B, C. These are in level 1 because there is a single edge before that level.

As like this,
D, G, E are in level 2.
F is in level 3.
I is in level 4.

BFS leveling
As per rule, we have to start from the root A and each of the levels we have to visit left to right from level 0.  So, 

Visiting Level 0 we get - A

Visiting Level 1 we get - A, B, C
Visiting Level 2 we get - A, B, C, D, G, E
Visiting Level 3 we get - A, B, C, D, G, E, F
Visiting Level 4 we get - A, B, C, D, G, E, F, I

 So, finally, we found the path-

A, B, C, D, G, E, F, I

This is called level order traversal and it is from left to right. 

Post a Comment