Breadth First Search in Artificial Intelligence

Breadth First Search:

In the Breadth-First Search technique, the root node is expanded first, then all of its successors are expanded then their successors and so on. In BFS, all nodes are expanded at a given depth in the search tree before any nodes at the next level are expanded. It means that all immediate children of nodes are explored before any of the children’s children are considered.

Breadth First Search Algorithm:

Step-1: Put the start (initial) node on a list that is called OPEN of unexplored nodes. If the start node is a goal node, a solution has been found.

Step-2: If(OPEN is empty) or (OPEN=GOAL) then no solutions exist, So, terminate the search.

Step-3: Remove the first node a, from OPEN and place it in a list called CLOSED of expanded nodes.

Step-4: Expand node If it has no successor Then go to Step 2.

Step-5: Place all successors of node a, at the end of OPEN.

Step-6: If any of the successors of node a, is a goal state then a solution is found.