Breadth-First Search

Breadth-first search explores a graph level by level from a source, finding shortest paths in unweighted graphs in O(V + E).

Explore in rings

Breadth-first search (BFS) starts at a source vertex and visits all its neighbours, then all their unvisited neighbours, and so on. It fans outward in rings of increasing distance. A queue holds the frontier: vertices are dequeued in the order discovered, and each newly found vertex is marked visited and enqueued.

Shortest paths for free

Because BFS visits vertices in order of their distance from the source, the first time it reaches a vertex is along a shortest path measured in number of edges. Recording each vertex's discoverer lets you reconstruct that path. This makes BFS the natural shortest-path algorithm for unweighted graphs.

• Time: O(V + E) with an adjacency list
• Space: O(V) for the queue and visited set
• Finds shortest paths in unweighted graphs
• Explores nearest vertices first

from collections import deque
def bfs(graph, src):
    dist = {src: 0}
    q = deque([src])
    while q:
        u = q.popleft()
        for v in graph[u]:
            if v not in dist:
                dist[v] = dist[u] + 1
                q.append(v)
    return dist

Correctness in one line

BFS visits vertices in non-decreasing order of distance from the source, so a vertex's recorded distance is final the moment it is discovered. The proof rests on the queue holding, at any time, vertices of at most two adjacent distance levels, which keeps the frontier ordered. This is why a plain FIFO queue, not a priority queue, suffices when all edges have equal weight.

Where BFS is used

BFS underlies shortest-hop routing, web crawling that prioritises nearby pages, finding connected components, testing bipartiteness by two-colouring, and computing the diameter of a network. It is also the search order in many puzzle solvers where every move has equal cost. When edges carry different weights, BFS no longer finds shortest paths and you need Dijkstra's algorithm instead.