Breadth-First Search and Shortest Path Layers in Python

Preamble

BFS explores layer by layer—distance 0, then 1, then 2. On unweighted graphs, the first visit to a node is along a shortest path in edge count. collections.deque gives O(1) pops from the front; list.pop(0) does not.

deque-based BFS

from collections import deque

def bfs_layers(graph, start):
    q = deque([start])
    seen = {start}
    while q:
        v = q.popleft()
        yield v
        for nbr in graph.get(v, ()):
            if nbr not in seen:
                seen.add(nbr)
                q.append(nbr)

For shortest path, store parent maps when you need reconstruction—not only seen.

Why not list.pop(0)?

Popping the front of a Python list is O(n) due to shifting elements—deque exists precisely for queue workloads.

Conclusion

Pair BFS with parent pointers for paths; pair DFS when you must exhaust branches or use coloring tricks. Black, isort, and mypy as a Python Quality Loop adds Black, isort, and mypy as a quality loop.