Breadth-First Search (BFS)
A 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.
Breadth-First Search (BFS)
Queue State (FIFO)
Queue ensures level-by-level exploration, guaranteeing shortest path
Ready to start
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
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