## Definition **Breadth-First Search (BFS)** is an [[Uninformed Search]] algorithm that expands nodes in increasing order of depth from the root. Implemented with a **FIFO queue**. ## Algorithm ``` frontier ← FIFO queue with the initial state explored ← ∅ while frontier is non-empty: node ← dequeue(frontier) if isGoal(node.state): return path(node) explored.add(node.state) for each action a in A(node.state): child ← expand(node, a) if child.state not in explored and not in frontier: enqueue(frontier, child) return failure ``` ## Properties - **Complete:** yes, if the branching factor $b$ is finite. - **Optimal:** yes, when all actions have the same cost. With variable costs, use [[Uniform Cost Search]] instead. - **Time:** $O(b^d)$ where $d$ is the depth of the shallowest goal. - **Space:** $O(b^d)$ — the killer. Every node at the goal's depth lives in the frontier. ## Why Space Hurts For a chess-like problem ($b \approx 35$, $d \approx 10$), BFS needs ~$35^{10} \approx 2.7 \cdot 10^{15}$ states in memory. Not feasible. This is why [[Iterative Deepening Search]] often replaces BFS in practice: IDS trades a small time overhead for $O(bd)$ space. ## When to Use - Shallow solutions and small state space (puzzle solvers, social graph queries). - Uniform action costs. - When optimality of the shallowest solution matters. ## Related - [[Uninformed Search]] - [[Depth-First Search]] - [[Iterative Deepening Search]] - [[Uniform Cost Search]]