Part 5: Graph Traversal I — Breadth-First Search

A Bit of History

Breadth-first search was independently discovered at least twice for very different purposes. In 1959, American computer scientist Edward F. Moore described a layer-by-layer search to find the shortest path through a maze — his paper, fittingly titled "The shortest path through a maze," is one of the earliest published uses. Around the same time, C. Y. Lee (a researcher at Bell Labs) independently devised essentially the same method in 1961 for a very unglamorous but hugely consequential problem: routing wires on a printed circuit board without crossing paths. To this day, "Lee's algorithm" is the name still used in the electronic-design-automation industry for grid-based wire routing — the same queue-driven, ring-by-ring search you now know as BFS.

Breadth-First Search (BFS): The Core Guarantee

Recall from the BFS deep dive: Breadth-First Search (BFS) explores a graph layer by layer starting from a source vertex \(s\), using a First-In, First-Out (FIFO) queue to discover nodes in strict order of increasing distance.

The single most important property to remember: when BFS completes, \(\text{dist}[v]\) is guaranteed to equal the exact unweighted shortest path distance from \(s\) to \(v\) for every reachable vertex \(v\). Every application, algorithm, and structural proof in this section relies directly on this single guarantee.

Core Applications

Connected Components

Recall the equivalence relation from Part 1: \(u \sim v\) iff a path exists between them, and its equivalence classes are the graph's connected components. BFS computes this relation directly: run BFS from any unvisited vertex, and every vertex it reaches belongs to the same component. Repeat from any remaining unvisited vertex until none are left. Total cost across the whole graph is still \(O(V+E)\), since each vertex and edge is examined exactly once across all the BFS runs combined.

Testing Bipartiteness

Part 4 previewed the claim: a graph is bipartite if and only if it has no odd cycle. BFS gives the constructive half of that proof. Run BFS from any vertex, and 2-color every vertex by the parity of its BFS layer — even layers get color 0, odd layers get color 1. Because BFS visits a vertex only once, this coloring is well-defined. The graph is bipartite exactly when no edge connects two same-colored vertices.

from collections import deque, defaultdict

def is_bipartite(adj, source):
    """Returns (bipartite: bool, coloring: dict) using BFS layer parity."""
    color = {source: 0}
    queue = deque([source])
    while queue:
        u = queue.popleft()
        for v in adj[u]:
            if v not in color:
                color[v] = 1 - color[u]
                queue.append(v)
            elif color[v] == color[u]:
                return False, color   # same-color edge found -> odd cycle exists
    return True, color

adj = defaultdict(list, {"A": ["B", "D"], "B": ["A", "C"], "C": ["B", "D"], "D": ["C", "A"]})
print(is_bipartite(adj, "A"))  # (True, {'A': 0, 'B': 1, 'D': 1, 'C': 0}) -- it's a 4-cycle

BFS for Web Crawling

Model the web as a directed graph: pages are vertices, hyperlinks are edges. A crawler starting from a set of seed URLs uses BFS almost verbatim — a frontier queue of discovered-but-unvisited URLs, a visited set (with URL normalization to avoid treating example.com/ and example.com as different vertices), and level-by-level expansion. The BFS property that matters here isn't shortest paths — it's breadth-first prioritization: a crawler wants to discover many distinct sites early rather than tunnel deep into one site's link structure first (which a DFS-style crawler would do). Production crawlers add rate limiting ("politeness" — don't hammer one server), distributed frontier queues across many machines, and re-crawl scheduling, but the discovery order underneath is still BFS.

Advanced BFS Variants

Multi-source BFS starts with several sources already in the queue at distance 0 instead of one — useful for "distance to the nearest of these K locations" problems (nearest hospital, nearest exit). It is exactly ordinary BFS on a graph with an added virtual super-source connected to every real source with weight-0 edges.

Bidirectional BFS runs two BFS searches simultaneously — one forward from the source, one backward from the target — and stops the moment their frontiers meet. Since each search only needs to reach roughly half the true distance, this can reduce a search visiting \(O(b^d)\) vertices (branching factor \(b\), depth \(d\)) down to roughly \(O(2b^{d/2})\) — a dramatic saving on graphs with high branching factor, like word-ladder puzzles or friend-of-friend social searches.

0-1 BFS

A clever hybrid for graphs whose edges are weighted only 0 or 1 (common in grid problems — "some moves are free, some cost one step"): instead of a plain queue, use a deque. Push weight-0 edges to the front and weight-1 edges to the back. This keeps the deque's contents sorted by distance at all times without needing a full priority queue, giving Dijkstra-correct shortest paths in plain \(O(V+E)\) time — strictly faster than paying for a binary heap's \(O(\log V)\) factor when weights are this restricted.

Exercises

1. Prove that the connected-components algorithm above really does run in \(O(V+E)\) total time across the whole graph, not \(O(V+E)\) per component.
2. Trace the bipartiteness test on \(K_{3,3}\) and confirm it's bipartite, then add a single edge within one side and confirm the algorithm now reports "not bipartite."
3. Explain precisely why bidirectional BFS's stopping condition ("frontiers meet") is not simply "either search reaches the other's start vertex" — what could go wrong with that naive stopping rule?
4. Challenge: Implement 0-1 BFS using a deque and verify it produces the same distances as Dijkstra's algorithm (from the Dijkstra deep dive) on a graph where every edge weight is 0 or 1.

Conclusion & Next Steps

BFS's one guarantee — visiting vertices in strict order of distance — turns out to prove bipartiteness, compute connected components, and (in its bidirectional and 0-1 forms) solve harder shortest-path variants without ever needing a priority queue. Next, we turn to BFS's stack-based sibling and see what a completely different exploration order reveals about a graph's structure.