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 nod...

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.

BFS

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.

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

BFS

Problem:
Goal node = I

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.

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

Then,

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.