Breadth-First Search
Interactive lab
Try it: Breadth-First Search
How breadth-first search visits a graph in rings of increasing distance from a start node, using a queue.
How it works
- Mark the start node as seen and put it in a queue.
- Take the node at the front of the queue and visit it.
- Add each of its neighbours that has not been seen yet to the back of the queue, one level further out.
- Repeat until the queue is empty. Nodes never reached are not connected to the start.
Default run (26 steps): Start BFS at A. 8 edges switched on. … Queue empty — BFS finished. Order: A → B → D → C → E → G → F. Unreachable from A: H.
Educational simulation
Loading the simulation…