Graphs 0/61

BFS: breadth-first layers and shortest routes · 1 of 1

Breadth-first search

Use a first-in-first-out queue to visit vertices in distance layers and find fewest-move routes in graphs, grids and puzzle states.

4,838 words · 22 min read

Part 1 of 9 Breadth-first search

The order of the search

Breadth-first search finds the computers in order of how far they are from the start: first the start itself, then every computer one connection away, then every computer two connections away, and so on until nothing new turns up. Here is the sample with each computer drawn under its distance from computer 1:

1distance 02distance 13distance 14distance 15distance 2

The search finds computer 1, then 2, 3 and 4, then 5. Each computer is found once, at the smallest number of connections that reaches it (we will see why once the search is written down). So when computer nn is found, we know the length of the shortest route to it.

To write the search as a program we need two things: a way to store the network so that the computers next to a given one are quick to look up, and a way to visit the computers in this order.