Breadth-first search (BFS)

Drop a stone in a pond and the ripples spread out evenly in rings. Breadth-first search explores a graph the same way: first everything one step from the start, then everything two steps away, and so on. That simple order is what makes it find shortest paths.

A graph of lettered nodes coloured in rings by their distance from the start node, with a queue of nodes drawn underneath
A graph of lettered nodes coloured in rings by their distance from the start node, with a queue of nodes drawn underneath

The idea

A graph is a set of nodes joined by edges: places and roads, people and friendships, squares of a maze and the openings between them. Breadth-first search answers the question: starting here, what can I reach, and in how few steps? It keeps a queue of nodes still to visit. Taking nodes from the front and adding new ones at the back means the nodes are handled in the order they were discovered.

Step by step

Put the start in the queue at distance 0. Take the node at the front. For each neighbour that has not been seen, record its distance as one more than the current node, remember the current node as the way it was reached, and add it to the back of the queue. Skip neighbours that were seen before. Repeat until the queue is empty, or until the goal is reached.

An example

Take a graph with the edges A–B, A–C, B–D, C–D, C–E and D–F, and start at A. Taking A from the queue finds B and C at distance 1. Taking B finds D at distance 2. Taking C finds that D was already seen, and E at distance 2. Taking D finds F at distance 3. E and F find nothing new, and the queue is empty. Following the remembered nodes back from F gives F ← D ← B ← A, so a shortest path from A to F is A → B → D → F, three edges long.

Why the distances are right

Every node at distance 1 enters the queue before any node at distance 2, every node at distance 2 before any at distance 3, and so on, because a node's neighbours are only queued when the node itself comes off the queue. So the first path that reaches a node is one with the fewest edges, and BFS never needs to correct a distance. Each node is taken once and each edge looked at from both ends, so the work grows with the number of nodes plus the number of edges.

History and uses

Konrad Zuse described breadth-first search in 1945, in work on his Plankalkül language that was not published until 1972. Edward F. Moore reinvented it in 1959 to find the shortest path out of a maze, and C. Y. Lee used it in 1961 to route wires on circuit boards. Today it finds the fewest moves in puzzles, the degrees of separation in social networks, the pages a web crawler reaches first, and the nearest free cell in games. When edges have lengths, Dijkstra's algorithm generalises it.

Konrad Zuse (centre, with glasses) and Heinz Billing (left) at the SYSTEMS ’91 exhibition in Munich. Zuse described breadth-first search in 1945, in work on his Plankalkül language that was not published until 1972.
Konrad Zuse (centre, with glasses) and Heinz Billing (left) at the SYSTEMS ’91 exhibition in Munich. Zuse described breadth-first search in 1945, in work on his Plankalkül language that was not published until 1972.

Explore it

Open the app and press Step. The node being visited is highlighted, nodes waiting in the queue are blue, and visited nodes are green, each with its distance. The queue is shown under the graph, front first. Switch the click to Goal and pick a node to stop there and see the shortest path, or make a new graph with more nodes and edges.

Frequently asked questions

What is the time complexity of BFS?

O(V + E) for V nodes (vertices) and E edges: each node enters and leaves the queue once, and each edge is examined from both ends. It needs O(V) extra memory for the queue and the distances.

Why does BFS use a queue?

Because first in, first out keeps the nodes in the order they were discovered, which is the order of their distance. With a stack instead, the search would dive deep first: that is depth-first search.

Can BFS find shortest paths in weighted graphs?

Not in general: it counts edges, not their lengths. For weighted graphs with no negative edges, use Dijkstra's algorithm. If every weight is 0 or 1, a variant called 0-1 BFS works.

Where is BFS used?

Solving puzzles and mazes in the fewest moves, finding friends of friends in social networks, crawling the web level by level, broadcasting in networks, and as a building block of other algorithms such as finding maximum flows.

Ready to try it?

Open PictorX in your browser — no install, no credit card required to start.

Try breadth-first search