Breadth First Search (BFS)

This is also a brute force search procedure like DFS. We are searching progresses level by level. Unlike DFS which goes deep into the tree. An operator employed to generate all possible children of a node. BFS being a brute force search generates all the nodes for identifying the goal.

ALGORITHM:

Step 1. Put the initial node on a list “START”

Step 2. If START is empty or goal terminate the search.

Step 3. Remove the first node from the Start and call this node “a”

Step 4. If a =”GOAL” terminate search with success

Step 5. Else if node “a” has successors generate all of them and add them at the tail of

“START”

Step 6. Go to step 2.

Advantages:

1. BFS will not get trapped exploring a blind alley.

2. If there is a solution then BFS is guaranteed to find it.

3. The amount of time needed to generate all the nodes is considerable because of the time complexity.

4. Memory constraint is also a major problem because of the space complexity.

5. The searching process remembers all unwanted nodes, which are not practical use for the search process.