Breadth-First Search (BFS)
Software Engineer path · lesson 21 of 99A fundamental graph traversal algorithm. It explores all neighbor nodes at the present depth prior to moving on to the nodes at the next depth level. It guarantees the shortest path in an unweighted graph.
Switch and compare the expanded-cells count.
Start at (4,1), goal (4,11).
- 1queue = [start]; seen = {start}
- 2while queue:
- 3 cell = queue.popleft() # oldest first
- 4 if cell == goal: return path
- 5 for nb in neighbours(cell):
- 6 if nb not seen: seen.add(nb); parent[nb] = cell; queue.append(nb)
- 7return "no path"
- Cells expanded
- 0 / 108
- Frontier pushes
- 1 / 110
Tap any element in the diagram to inspect its state at this step.
Keys: ← → step, Space play/pause. Predict mode pauses before key steps and asks what happens next.
Breadth-first, level by level
Order the steps of BFS from a source node.
Tap a piece, then tap where it goes — or drag it. Tap the tray to take one back.
- 1Drop a step here
- 2Drop a step here
- 3Drop a step here
- 4Drop a step here
- 5Drop a step here
Test your knowledge
Does BFS guarantee the shortest path?
The short version
Think of dropping a stone in a calm pond. Ripples spread out in circles, reaching everything at distance 1, then distance 2. BFS explores 'ripples' layer by layer.
In more depth
Layer by Layer
Breadth-First Search (BFS) is like a wave spreading out from a pebble dropped in water. It explores the graph layer by layer: first all neighbors at distance 1, then all neighbors at distance 2, and so on.
The Queue:
BFS uses a Queue (FIFO) data structure.
Shortest Path Guarantee
Because BFS explores layers sequentially, the first time it reaches a target node, it is guaranteed to be via the shortest path (in an unweighted graph).
When to reach for this
- Find the **Shortest Path** in an **Unweighted Graph** or Grid
- Level Order Traversal of a Tree
- Find all nodes connected to a source (Connected Components)
- State space search where the cost of each move is equal
Interview Questions
References & Further Reading
Love this visualization?
Sign up to track your progress, earn achievements, use the AI assistant, and access your personal learning dashboard.
100% free • No credit card required