Uninformed Search - Breadth-First Search (BFS)

BFS explores all nodes at the current depth level before moving to the next depth level (explore nodes in order of increasing depth).

• Completeness: Yes, when the branching factor is finite
• Optimality: Yes, when all the step costs are equal or in a unweighted graph. The shortest path in terms of the number of edges is also the lowest-cost path

Pseudocode

BFS(Graph, start, goal):
    1. Create a queue named Q and enqueue (start)
    2. Create an empty set named visited to store visited nodes
    3. While Q is not empty:
        a. Dequeue the node (current) from Q
        b. If current is the goal, return the path
        c. If current is not visited:
            i. Add current to visited set
            ii. For each neighbor (next) of current:
                - If next is not visited:
                    - Enqueue next to Q
    4. If goal is not found, return failure

Time complexity

When branching factor is $b$, and the depth of the goal node is $d$.

• Level 0: 1 node (initial state).
• Level 1: $b$ nodes.
• Level 2: $b^2$ nodes.
• Level d: $b^d$ nodes (worst-case, when the goal is at depth $d$).
• The total number of nodes explored is (Sequence and Series): $1+b+b^2+...+b^d=O(b^d)$

Space complexity

BFS stores all nodes at the current level before moving to the next level. In a tree search, the number of nodes grows exponentially at each level.

• Level 0: 1 node (initial state).
• Level 1: $b$ nodes.
• Level 2: $b^2$ nodes.
• Level d: $b^d$ nodes (worst-case, when the goal is at depth $d$).
• The total number of nodes explored is: $1+b+b^2+...+b^d=O(b^d)$

---

Back to parent page: Problem Solving and Search

AI AI_Algorithm Problem_Solving Uninformed_Search BFS