**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:

Goal node = I

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.

## 0 Comments