Breadth-First Search

A Brute-force Approach

Given: Graph, start node, goal node.

1. Begin search at the start node and do a test for goal.
   1. If start is same as goal, then stop search.
   2. Otherwise, continue search.
2. Visit the adjacent nodes of start and test whether any of them is goal.
3. If goal not found, then continue search at the adjacent nodes of the nodes visited in previous step. Skip any node that has already been visited.
4. Continue Step 3, until either the goal is found or until all nodes that can be reached from start node have been visited.

Exhaustive or brute-force search strategy

• Enumerate systematically all possible candidates and test if any of them is the goal.
• In breadth-first search, all paths of length ‘n’ from start are

Inplementaion

Creates and maintains three lists:

1. A list of visited nodes. I These nodes have failed the test for goal node.
2. A list of frontier nodes. I Frontier nodes are the neighbours of already visited nodes that have not been visited (goal-tested) yet.
3. A list of predecessor nodes. I Predecessor is recorded when a node is expanded, i.e. when its neighbours are added to the frontier list.

Pros

• Simple and easy to implement.
• If a path exists from start to goal, it will always find the shortest path (complete and optimal).
• Suitable for smaller grids (fewer cells).

Cons

• Searches ‘blindly’. Only adjacency or neighbourhood information is used. (Uninformed search)
• Inefficient, especially for large grids populated sparsely with obstacles.