Breadth-First Search

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


Return to Articles