Breadth-first search (BFS)

Applies to: general

BFS explores a graph in waves outward from a start, using a queue (FIFO). It visits nearer nodes first, so in an unweighted graph the first time it reaches the goal is via a shortest path.

from collections import deque
q = deque([start]); seen = {start}
while q:
    node = q.popleft()
    for nb in neighbors(node):
        if nb not in seen: seen.add(nb); q.append(nb)

See also: graph, queue, dfs, big-o