Breadth-first search

How a maze solver finds the shortest route without trying every path

Breadth-first search (BFS) explores a graph, meaning dots (nodes) joined by lines (edges), ring by ring. It visits everything one step from the start, then everything two steps away, then three, and so on.

Take a small friend network: You know Bea and Cal. Bea knows Dan and Eve, Cal knows Eve and Fay, and Dan knows Gus. BFS visits You (ring 0), then Bea and Cal (ring 1), then Dan, Eve and Fay (ring 2), then Gus (ring 3).

Because rings grow outward, BFS first reaches each node by a shortest route, counted in edges. In a maze, squares are nodes and open moves are edges, so the ring where BFS meets the exit is the fewest moves.

Breadth-first search

LinkedIn's '2nd' and '3rd' badges are rings around you

LinkedIn labels people as 1st, 2nd or 3rd connections. That label is exactly the ring BFS would put them in, starting from you: 1st are your contacts, 2nd are contacts of contacts, 3rd are one more step out.

Eve would show as '2nd' even though she is reachable through both Bea and Cal: BFS records her the first time it meets her, at ring 2, and ignores the later route.

Breadth-first search

A waiting line makes sure nearer people are always visited first

BFS keeps a queue, a first-in-first-out line, of nodes found but not yet expanded, plus a 'seen' set. It takes the node at the front, puts its unseen neighbours at the back, marks them seen, and repeats.

The queue is the trick: every ring-1 node joins before any ring-2 node, so ring k finishes before ring k+1 and first finds are shortest. The 'seen' set stops loops like You–Bea–Eve–Cal repeating forever.

Each node enters the queue once and each edge is looked at once from each end, so BFS takes O(V + E) time for V nodes and E edges. The catch: it counts hops, not lengths, so a road with a 50 km edge counts the same as a 1 km edge.