Step by step
The example above, written out — the same steps the animation plays.
- 1Start at A. BFS explores level by level, using a queue (first in, first out). A goes in first.
- 2Visit A. A leaves the front of the queue.
- 3Queue B. B is new: add it to the back of the queue.
- 4Queue C. C is new: add it to the back of the queue.
- 5Visit B. B leaves the front of the queue.
- 6A already seen. A is already visited or queued — skip it.
- 7C already seen. C is already visited or queued — skip it.
- 8Queue D. D is new: add it to the back of the queue.
- 9Visit C. C leaves the front of the queue.
- 10A already seen. A is already visited or queued — skip it.
- 11B already seen. B is already visited or queued — skip it.
- 12D already seen. D is already visited or queued — skip it.
- 13Queue E. E is new: add it to the back of the queue.
- 14Visit D. D leaves the front of the queue.
…and 12 more steps — press Play above to watch them all.
What's happening?
- Put the start node in a queue and mark it seen.
- Take the node at the front of the queue and visit it.
- Add each of its neighbours that has not been seen to the back of the queue; repeat until the queue is empty.
Complexity
- Time
- O(V + E) — every node and edge once
- Space
- O(V) for the queue and the seen set
Where you'll meet it
Shortest paths when every step costs the same (fewest hops, fewest moves in a puzzle), "people you may know" (friends of friends), web crawlers and network broadcast.
Common mistake
Marking a node as seen only when it is visited instead of when it is queued — the same node then gets queued many times.
FAQ
Why does BFS find the shortest path?
It reaches every node at distance 1 before any at distance 2, so the first time it reaches a node is by the fewest edges.
BFS vs DFS?
BFS uses a queue and spreads out evenly; DFS uses a stack (or recursion) and goes deep first. Compare them on the same graph here.
Does BFS work with weighted edges?
Not for shortest paths — use Dijkstra when edges have different costs.