ƒ(x) GraphIntermediate interactive
Breadth-First Search
Explore level by level with a queue.
graph_bfs
step 1 / 13
Start BFS at A. Enqueue it.
frontiercurrentvisited
speed1×
How it works
BFS explores a graph in expanding rings: all neighbors at distance 1, then distance 2, and so on, using a queue. On unweighted graphs it finds the shortest path in edges, and it's the basis for level-order tree traversal.
Mental models
- A FIFO queue enforces the level-by-level order.
- First time you reach a node is the shortest unweighted path.
Complexity
- Time
- O(V + E)
- Space
- O(V)queue + visited
Reach for it when
- Shortest path (unweighted)
- Level-order traversal
- Web crawling