Breadth-First Search, Visually

Depth-first search gets all the attention because it’s the one you can write in four lines with a stack, and your call stack does the bookkeeping for free. Breadth-first search asks for a little more discipline, an explicit queue, but it buys you something DFS can’t give: the first time you reach a node, you’ve reached it by the shortest path, measured in number of edges.

The graph

Take this small graph, six nodes, undirected:

Starting a breadth-first search from $A$, the queue empties out in the order $A, B, C, D, E, F$: everything one edge away from $A$ gets visited before anything two edges away, which is exactly the guarantee the algorithm exists to provide.¹

The algorithm

from collections import deque

def bfs(graph, start):
    visited = {start}
    order = []
    queue = deque([start])
    while queue:
        node = queue.popleft()
        order.append(node)
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)
    return order

graph = {
    "A": ["B", "C"],
    "B": ["A", "D", "E"],
    "C": ["A", "D", "F"],
    "D": ["B", "C", "E"],
    "E": ["B", "D"],
    "F": ["C"],
}

print(bfs(graph, "A"))
# ['A', 'B', 'C', 'D', 'E', 'F']

Why the queue matters

Swap the queue for a stack and you’ve written depth-first search instead: same skeleton, different discipline about which frontier node gets explored next. The complexity is the same either way, $O(V + E)$: every vertex is enqueued once and every edge is inspected at most twice, once from each endpoint, so the work is linear in the size of the graph, not exponential in its depth. What you’re paying for with BFS is the queue itself: in the worst case, a wide, shallow graph, it can hold $O(V)$ nodes at once, where DFS’s recursion stack only ever holds one path’s worth.