BreadthFirst Search
Published
Completeness 
 
Complete if the branching factor is finite. 
Optimality 
 
Optimal if the costs of all actions are equal. 
Time Complexity 
 
O(b^{d}) 
Space Complexity 
 
O(b^{d}) 
Visual Example

Current Node 
Frontier 
A 
B, C 
B 
C, D, E 
C 
C, D, E, F 
Goal Node Found 

 We start from the root node A.
 We check to see if A is a goal node. It's not, so we add it's children to the frontier.
 We check to see if B is a goal node. It's not, so we add it to the frontier.
 We check to see if C is a goal node. It's not, so we add it to the frontier.
 We remove node B from the frontier and then we add it's children to the frontier.
 We check to see if D is a goal node. It's not, so we add it to the frontier.
 We check to see if E is a goal node. It's not, so we add it to the frontier.
 We remove node C from the frontier and then we add it's children to the frontier.
 We check to see if F is a goal node. It's not, so we add it to the frontier.
 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, BreadthFirst Search does not reexplore nodes that are in the frontier or which have already been explored.
Return to Articles