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.
- O(V + E)
- space O(V)
- queue
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.
Queue: first in, first out. BFS always takes the vertex that has waited longest.
Other terms on this page
- 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.
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.