Course contentsShow
← Computer Science
Lesson 2741 of 2,87261. AI and Search AlgorithmsFree lesson

BFS Implementation and Complexity

Queue-based implementation with O(b^d) time and space complexity analysis.

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

  1. Start with the initial state in a queue
  2. 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.