BFS Implementation and Complexity
You'll learn: How to implement Breadth-First Search using a queue and why its time and space complexity are both O(b^d).
The Core Idea
Breadth-First Search explores all nodes at distance d from the start before moving to distance d+1. The queue is the data structure that makes this work: it processes nodes in first-in-first-out (FIFO) order, ensuring we explore level by level.
Think of it like ripples spreading in a pond. The first ripple (initial state) goes in the queue. We process it, add all its neighbors (the next ripple), then move to those. Each "ripple" is a generation of nodes at the same depth.
Queue-Based Implementation Pattern
- Start with the initial state in a queue
- While the queue isn't empty:
- Dequeue the front node
- If it's the goal, return the solution
- Otherwise, add all its unexplored successors to the back of the queue
- Mark the node as explored
The queue guarantees we finish all nodes at depth d before touching depth d+1.
Complexity Analysis
Time Complexity: O(b^d)
- b = branching factor (number of successors per node)
- d = depth of the shallotest goal
- BFS explores 1 + b + b² + b³ + ... + b^d nodes (the entire tree up to depth d)
- This sums to O(b^d)
Space Complexity: O(b^d)
The frontier (queue) holds all nodes at the current level. At depth d, that's roughly b^d nodes simultaneously in memory—BFS's major limitation.
Key Takeaway: BFS guarantees the shortest path but requires O(b^d) memory because it stores an entire level of the search tree in its queue at once, making it memory-intensive for deep or wide search spaces.