Introduction to BFS
Explore data structures layer by layer using a Queue.
What is Breadth-First Search?
Breadth-First Search (BFS) is a fundamental graph and tree traversal algorithm.
Unlike DFS which dives deep, BFS explores the world layer by layer. Imagine dropping a stone in a pond; the ripples expand outwards in perfect circles. BFS is that ripple, visiting all neighbors at distance 1, then all at distance 2, and so on.
The Motivation: Shortest Path
The #1 reason to use BFS is to find the Shortest Path in an unweighted graph.
"Find the minimum number of steps to get from A to B."
Because BFS guarantees we visit nodes in order of their distance from the start, the first time we reach the target, we are guaranteed to have found the shortest path.
BFS vs DFS
Why not always use DFS?
- DFS might go 1000 steps down the wrong path before realizing the target was just 1 step to the right.
- BFS checks everything at distance 1 first.
Trade-off: BFS typically uses more memory (Queue stores an entire level) than DFS (Stack stores just a single path).
The Intuition: Queue (FIFO)
BFS logic utilizes a FIFO (First-In, First-Out) Queue.
- Enqueue the start node.
- Dequeue a node and Visit it.
- Enqueue all its unvisited neighbors.
This ensures that nodes discovered earlier (closer to start) are processed before nodes discovered later.
Interactive Walkthrough
Initializing...
See the Logic in Motion
Stop memorizing code. Unlock the full interactive visualizer to master the logic step-by-step.When should I use BFS?
Pattern Recognition Triggers:
Use BFS immediately if you see:
- "Shortest Path": Minimum steps, level, or distance.
- "Level Order Traversal": Printing trees row by row.
- "Connected Components": (Can use DFS too, but BFS is common).
- "Minimum Knight Moves" / "Rotting Oranges": Simultaneous expansion problems.
Stop Guessing, Start Mastering.
Build the FAANG intuition. Master this pattern with optimized implementations, visual dry runs, and our curated collection of high-yield problems.