Published
 Completeness - Complete if the branching factor is finite. Optimality - Optimal if the costs of all actions are equal. Time Complexity - O(bd) Space Complexity - O(bd)

## Visual Example Current Node Frontier
A B, C
B C, D, E
C C, D, E, F
Goal Node Found
1. We start from the root node A.
2. We check to see if A is a goal node. It's not, so we add it's children to the frontier.
1. We check to see if B is a goal node. It's not, so we add it to the frontier.
2. We check to see if C is a goal node. It's not, so we add it to the frontier.
3. We remove node B from the frontier and then we add it's children to the frontier.
1. We check to see if D is a goal node. It's not, so we add it to the frontier.
2. We check to see if E is a goal node. It's not, so we add it to the frontier.
4. We remove node C from the frontier and then we add it's children to the frontier.
1. We check to see if F is a goal node. It's not, so we add it to the frontier.
2. We check to see if G is a goal node. It is, so we're done.

## Algorithm Notes

• Abbreviated as BFS.
• Uses a FIFO queue for the frontier.
• The goal test is applied to each node as it is encountered, so the algorithm returns the path to the goal as soon as it's found.
• As with most graph searches, Breadth-First Search does not re-explore nodes that are in the frontier or which have already been explored.