Breadth-first search (BFS), explained

A graph is a set of points (nodes) joined by lines (edges). Breadth-first search starts at one node and visits all of its neighbours first, then all of their neighbours, spreading out like ripples in water.

Because it moves outwards one step at a time, the first time it reaches a node is along a path with the fewest edges.

How it works

• Put the start node in a queue and mark it as seen.
• Take the first node from the queue and visit it.
• Add all of its unseen neighbours to the back of the queue and mark them as seen.
• Repeat until the queue is empty.

A small example

Take these edges and start from A:

A-B  A-C  B-D  C-E  D-E

Visit order: A, B, C, D, E

B and C are one step from A, so they come before D and E.

What to know about its cost

• O(V + E) time, where V is the number of nodes and E the number of edges.
• Uses O(V) space for the queue.
• Finds the fewest-edge path in graphs where all edges count the same.

Where it works well

• Finds the shortest path when edges are unweighted.
• Good for "how far away is it?" questions.

Where it struggles

• Does not account for edge weights.
• The queue can grow large in wide graphs.

Try it yourself

Open the Graph Algorithms experiment, enter these edges (A-B, A-C, B-D, C-E, D-E), choose BFS and start from A, and step through it. Then try a different graph and watch how the result changes.

Open the Graph Algorithms experiment