Breadth-first traversal is a generalization of breadth-first tree traversal to all graphs. Instead of starting at a root node, we may start at any vertex and explore all vertices reachable from it.

Because of this, we must keep track of which vertices have already been visited to avoid infinite loops and repeated work.

As with trees, the standard implementation uses a queue to ensure vertices are visited in increasing order of distance (number of edges) from the start vertex.

The algorithm's time complexity is and will produce the shortest paths (in number of edges) from the start vertex

Implementation

Assume the graph is represented using an adjacency list.

from collections import deque

def breadth_first_traversal(graph, start, visit):
    visited = set()
    queue = deque([start])
    visited.add(start)

    while queue:
        v = queue.popleft()
        visit(v)

        for neighbor in graph[v]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

• Vertices are enqueued when discovered, not when dequeued
• visited prevents revisiting vertices via cycles
• All vertices at distance k are processed before any at distance k + 1

Traversing an Entire Graph

If the graph may be disconnected, we must run breadth-first traversal from every unvisited vertex.

from collections import deque

def breadth_first_traversal_all(graph, visit):
    visited = set()

    for start in graph:
        if start in visited:
            continue

        queue = deque([start])
        visited.add(start)

        while queue:
            v = queue.popleft()
            visit(v)

            for neighbor in graph[v]:
                if neighbor not in visited:
                    visited.add(neighbor)
                    queue.append(neighbor)

This guarantees:

• Every vertex is visited exactly once
• Each connected component is traversed in breadth-first order