Graph Traversal: BFS Explained

Breadth-First Search (BFS) explores a graph level by level — it visits every neighbor of the starting vertex first, then every neighbor of those neighbors, and so on, spreading outward in expanding rings rather than plunging deep down one path. That level-by-level order is exactly what makes BFS the right tool whenever you need the shortest path in an unweighted graph, or any kind of "closest first" exploration.

Why a Queue?

BFS relies on a queue — a FIFO (first-in, first-out) structure — to control the order vertices get visited. Every time you discover a new neighbor, it goes to the back of the queue; every time you're ready to visit a vertex, you take it from the front. Because earlier-discovered vertices always get processed before later-discovered ones, this naturally produces the level-by-level spread BFS is known for.

BFS Implementation

from collections import deque

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

def bfs(graph, start):
    visited = {start}
    queue = deque([start])
    order = []

    while queue:
        vertex = queue.popleft()
        order.append(vertex)

        for neighbor in graph[vertex]:
            if neighbor not in visited:
                visited.add(neighbor)   # mark visited when ENQUEUED, not when popped
                queue.append(neighbor)

    return order

print(bfs(graph, "A"))

Output:

['A', 'B', 'C', 'D', 'E']

Notice A's direct neighbors (B, C) are both visited before D, even though D is reachable from A through either of them — that's the level-by-level signature of BFS in action. One subtle but important detail: visited is marked the moment a vertex is enqueued, not when it's finally popped — marking it late can let the same vertex get queued multiple times through different paths.

Why BFS Finds the Shortest Path

Because BFS fully exhausts every vertex at distance 1 before looking at any vertex at distance 2, the first time it reaches any given vertex, it has necessarily done so via the shortest possible route (measured in number of edges). This only holds for unweighted graphs — if edges have different costs, you need a weighted shortest path algorithm like Dijkstra's instead.

You can see this working version used to solve a complete breadth-first search problem in the Python BFS program.

Complexity and Common Use Cases

BFS runs in O(V + E) time — every vertex is enqueued once, and every edge is examined once when looking at a vertex's neighbors — with O(V) space for the queue and visited set in the worst case.

Beyond shortest paths, BFS shows up anywhere "closest first" matters: finding the shortest number of hops between two people in a social network, web crawlers exploring a site level by level, and solving puzzles where each move counts equally (like a sliding puzzle or a maze with uniform step cost).