Breadth-first search

Applies to: general, python

Breadth-first search explores a graph level by level using a queue, visiting all nodes one edge away before going further. In an unweighted graph it finds the shortest path by number of edges.

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

See also: depth-first-search, queue