Breadth-first search

Explore in rings — every node at distance 1, then 2, then 3. The foundation of shortest paths in unweighted graphs.

Complexity: O(V + E) time · O(V) space

The idea

Breadth-first search is patient where DFS is eager: it finishes everything at the current distance before moving one step further out. Nodes are discovered in order of how many edges they are from the start.

That discovery order is why BFS finds shortest paths in unweighted graphs — the first time a node is reached is along a minimum-edge route.

The queue does the ordering

A first-in-first-out queue holds the frontier. Popping from the front and appending newly discovered neighbours to the back guarantees layer-by-layer processing; marking nodes visited when they are enqueued (not when they are popped) keeps duplicates out of the queue.

Watch for it on the canvas

On a tree the layers are literal: the root lights up, then its children, then grandchildren — a level-order sweep. On any graph you'll see the visited region grow outward like a ripple.

Try it on this graph:

# Breadth-first search from node "A" — the canvas animates on its own
# as the algorithm reads the graph through graph.getNeighbors().
from collections import deque

start = "A"
visited = {start}
queue = deque([start])

while queue:
    node = queue.popleft()
    print(node)
    for neighbour in graph.getNeighbors(node):
        if neighbour not in visited:
            visited.add(neighbour)
            queue.append(neighbour)

Open this post in a project to run it and watch the wavefront spread.