Table of Contents
BFS (Breadth First Search) is a traversing algorithm where you should start traversing from a selected node (source or starting node) and traverse the graph layer wise thus exploring the neighbour nodes (nodes which are directly connected to source node). You must then move towards the next-level neighbour nodes.
Concept of BFS
Step 1: Traverse the root node
Step 2: Traverse all neighbours of root node.
Step 3: Traverse all neighbours of neighbours of the root node.
Step 4: This process will continue until we are getting the goal node.
Algorithm of BFS
Step 1: Place the root node inside the queue.
Step 2: If the queue is empty then stops and return failure.
Step 3: If the FRONT node of the queue is a goal node then stop and return success.
Step 4: Remove the FRONT node from the queue. Process it and find all its neighbours that are in readystate then place them inside the queue in any order.
Step 5: Go to Step 3.
Step 6: Exit.
Advantages of BFS
1. The solution will definitely found out by BFS If there is some solution.
2. BFS will never get trapped in a blind alley, which means unwanted nodes.
3. If there is more than one solution then it will find a solution with minimal steps.
Disadvantages Of BFS
1. Memory Constraints As it stores all the nodes of the present level to go for the next level.
2. If a solution is far away then it consumes time.
Application Of BFS Algorithm
1. Finding the Shortest Path.
2. Checking graph with petiteness.
3. Copying Cheney’s Algorithm.
