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: define \(u \sim v\) to mean "a path exists between \(u\) and \(v\)." Checking the three equivalence-relation axioms confirms this is a legitimate equivalence relation, not just a convenient label:

• Reflexive: \(u \sim u\) — the empty path (zero edges) trivially connects a vertex to itself.
• Symmetric: if \(u \sim v\) then \(v \sim u\) — in an undirected graph, walking any path backwards is still a valid path.
• Transitive: if \(u \sim v\) and \(v \sim w\) then \(u \sim w\) — splice the two paths together through \(v\) to get a walk from \(u\) to \(w\), and every walk contains a genuine path.

For any vertex \(v\), its equivalence class is the set \([v] = \{u \in V : u \sim v\}\) — every vertex reachable from \(v\) by some path (and, by symmetry, every vertex from which \(v\) itself is reachable). The three axioms together guarantee that these classes behave exactly the way "components" should:

• Reflexivity guarantees every vertex belongs to some class — its own, at minimum — so no vertex is ever left out, unlabeled.
• Symmetry guarantees a class is well-defined no matter which vertex you start counting from: if \(u \in [v]\) then \(v \in [u]\), so \([u] = [v]\) — the class has no single "correct" starting point.
• Transitivity guarantees no two distinct classes can overlap. Suppose \([u]\) and \([v]\) shared some common vertex \(w\): then \(u \sim w\) and \(v \sim w\), so by symmetry \(w \sim v\), and by transitivity \(u \sim v\) — meaning \(u\) and \(v\) were secretly in the very same class all along, never two separate ones.

This is precisely the classical Fundamental Theorem of Equivalence Relations: every equivalence relation on a set induces a unique partition of that set into disjoint, exhaustive equivalence classes, and conversely, every partition of a set defines an equivalence relation ("same block as") that reproduces it. Applied here, it says \(\sim\) partitions \(V\) cleanly into disjoint equivalence classes — and those classes are exactly the graph's connected components. Every vertex lands in exactly one component: none is ever split across two, and no two components silently overlap.

BFS computes this partition directly, with no separate machinery required:

1. Pick any vertex that hasn't been visited yet and run BFS from it.
2. Every vertex BFS reaches during this run is, by definition, path-connected to the starting vertex — so all of them belong to the same equivalence class. Label them all with the current component number.
3. When that BFS run's queue empties, the entire component has been fully labeled. If unvisited vertices remain, pick any one of them and repeat from step 1 with the next component number.
4. Stop once every vertex has been visited and labeled.

from collections import deque, defaultdict

def connected_components(adj, vertices):
    """Labels every vertex with a component id using repeated BFS."""
    component_of = {}
    component_id = 0
    for start in vertices:
        if start in component_of:
            continue  # already labeled by an earlier BFS run
        component_of[start] = component_id
        queue = deque([start])
        while queue:
            u = queue.popleft()
            for v in adj[u]:
                if v not in component_of:
                    component_of[v] = component_id
                    queue.append(v)
        component_id += 1
    return component_of, component_id  # vertex -> component label, total count

adj = defaultdict(list, {"A": ["B"], "B": ["A"], "C": ["D"], "D": ["C"], "E": []})
labels, count = connected_components(adj, ["A", "B", "C", "D", "E"])
print(labels, count)  # {'A': 0, 'B': 0, 'C': 1, 'D': 1, 'E': 2} -- 3 components

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

Ordinary BFS works because every edge effectively costs 1. The moment edges have different costs, FIFO order is no longer enough. The special case of costs 0 and 1 is just structured enough that a deque can restore the correct distance order without a full priority queue.

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.