Breadth-first search (BFS)
Explores a graph layer by layer. A queue decides which vertex comes next, so the closest vertices are always visited first.
- time O(V + E)
- space O(V)
- uses a queue
What do these mean?
- Vertex: a point of the graph, drawn here as a circle with a letter.
- Edge: a line that joins two vertices. Here you can walk along it both ways.
- Neighbours: the vertices joined to a vertex by an edge. They are looked at in alphabetical order.
- Queue: first in, first out. BFS always takes the vertex that has waited longest.
- Stack: last in, first out. DFS always goes on from the vertex it reached last.
- V and E: the number of vertices and edges. O(V + E) means each vertex and each edge is handled a fixed number of times.
- in the queue
- current
- done
- search tree edge
- skipped edge
Start from A. Press play or step through the search.
Space: play or pause. Left and right arrows: step. Home and End: jump.
Try this: Pick the graph with two parts. The vertices that are not connected to the start are never reached.
How it works
BFS puts the start vertex in a queue. Then, again and again, it takes the vertex at the front of the queue and adds its new neighbours to the back. A queue serves in arrival order, so every vertex one edge away is finished before any vertex two edges away. The number next to a vertex is its distance from the start: the fewest edges needed to reach it.
When it is a good choice
Use BFS when you need the shortest way in steps: the fewest moves in a puzzle, the fewest hops in a network, the people within two connections of you. On a big graph the queue can get long, because it holds a whole layer at once.