Lab 03 — Bidirectional BFS on Implicit Graphs

Goal

Implement bidirectional BFS to find shortest paths in implicit state graphs, cutting the explored node count from O(b^d) to O(b^(d/2)) — the difference between timing out and finishing in milliseconds on Word Ladder-class problems.

Background

One-directional BFS from the start explores b^d nodes for branching factor b and distance d. Searching simultaneously from start and goal, stopping when the frontiers meet, explores ~2·b^(d/2). For b = 25, d = 10: 25^10 ≈ 10^14 vs 2 × 25^5 ≈ 2 × 10^7 — seven orders of magnitude.

Requirements to apply it:

  • The goal state is known explicitly (not just a predicate)
  • Moves are invertible (or the reverse graph is available)

Relation to phase-03 lab-09 (meet-in-the-middle): same halving idea, different object — that one splits a set to enumerate combinations in 2^(n/2); this one splits a path to search in b^(d/2). Kociemba’s two-phase solver (lab-02) is the industrial-strength descendant: instead of a backward frontier held in memory, the “backward half” is precomputed into pruning tables.

Interview Context

  • Standard FAANG: yes — Word Ladder (LC 127), Minimum Genetic Mutation (LC 433), Open the Lock (LC 752) are real, recurring questions, and bidirectional BFS is the expected senior-level answer
  • Codeforces / ICPC: occasional, usually as meet-in-the-middle on states
  • Search/planning roles: assumed knowledge
  • This is the most interview-relevant lab in Phase 13 — if you cherry-pick one, pick this

When to Skip This Topic

Skip if any of these are true:

  • You can’t write clean one-directional BFS with level tracking from memory (Phase 4 Lab 01 first)
  • You’re still failing Medium graph problems — this is an optimization on top of a pattern you must already own

Unlike the rest of this phase, most candidates targeting Hard-level interviews should not skip this.

Problem Statement

Word Ladder (LeetCode 127).

Given beginWord, endWord, and a dictionary wordList, return the number of words in the shortest transformation sequence from beginWord to endWord, changing one letter at a time, with every intermediate word in the dictionary. Return 0 if impossible.

Constraints

  • 1 ≤ word length ≤ 10
  • 1 ≤ len(wordList) ≤ 5000
  • All words same length, lowercase; endWord must be in the list
  • Generalization to plan for: state graphs with 10^6+ implicit nodes

Clarifying Questions

  1. Is beginWord required to be in the dictionary? (No.)
  2. Return the length or the actual path? (Length here; path needs parent pointers — see Follow-ups.)
  3. Count of words or count of edges? (Words: hit→cog ladder of 4 changes = 5.)
  4. Are moves symmetric? (Yes — changing one letter is invertible; this is what makes bidirectional legal.)

Examples

begin = "hit", end = "cog"
wordList = ["hot","dot","dog","lot","log","cog"]
→ 5   (hit → hot → dot → dog → cog)

Frontier sizes, one-directional from “hit”: 1 → 1 → 2 → 4 → 2. Bidirectional: forward {hit}→{hot}, backward {cog}→{dog,log}; forward {hot}→{dot,lot} … meets after ~half the levels with strictly smaller frontiers. On adversarial dictionaries (dense neighborhoods), the gap is exponential.

begin = "hit", end = "cog", wordList without "cog" → 0

Brute Force

One-directional BFS, generating neighbors by trying all 26 letters in every position, checking dictionary membership.

Brute Force Complexity

  • Time: O(N · L · 26) node expansions in the worst case over the whole graph — passes LC 127, but explores the full b^d cone; dies on larger state spaces
  • Space: O(N)

Optimization Path

  1. Wildcard buckets: precompute h*t → [hot, hat, ...] — maps each word to neighbors in O(L) lookups instead of O(26·L) probes.
  2. Two frontiers: sets front (from begin) and back (from end), plus a combined visited set.
  3. Always expand the smaller frontier — swap before each level. This is what guarantees b^(d/2): the expanded side never grows past the meeting point.
  4. Meet condition: while generating a neighbor, if it’s in the other frontier, the ladders join — return steps_forward + steps_backward.
  5. Frontiers as sets, not queues — level-by-level expansion replaces the FIFO.

Final Expected Approach

from collections import defaultdict
from string import ascii_lowercase

def ladder_length(begin, end, word_list):
    words = set(word_list)
    if end not in words:
        return 0

    buckets = defaultdict(list)
    for w in words | {begin}:
        for i in range(len(w)):
            buckets[w[:i] + "*" + w[i+1:]].append(w)

    front, back = {begin}, {end}
    visited = {begin, end}
    length = 1

    while front and back:
        if len(front) > len(back):
            front, back = back, front
        length += 1
        next_front = set()
        for word in front:
            for i in range(len(word)):
                for nb in buckets[word[:i] + "*" + word[i+1:]]:
                    if nb in back:
                        return length
                    if nb not in visited:
                        visited.add(nb)
                        next_front.add(nb)
        front = next_front

    return 0

Generic template for any implicit graph: replace the bucket lookup with a neighbors(state) function; keep separate dist_f / dist_b dicts instead of one visited set when you need the path or the graph is directed (use reverse moves for the backward side).

Data Structures

  • Two frontier sets + one visited set (or two distance dicts)
  • Wildcard-pattern buckets: dict pattern → list of words (precomputed adjacency)

Correctness Argument

  • BFS invariant per side: after k expansions, a frontier contains exactly the states at distance k from its origin.
  • If a shortest path of length d exists, its middle state is at distance ⌈d/2⌉ from one side and ⌊d/2⌋ from the other; alternating expansion of the smaller frontier reaches the meet before either side exceeds ⌈d/2⌉ levels.
  • The meet check happens on generated neighbors against the opposite frontier, so the returned length counts both halves exactly once — no path can be shorter, since both sides expanded strictly level-by-level.
  • One shared visited set is safe only because the meet check precedes it; a state claimed by one side that the other side needs would otherwise be silently swallowed (see Common Bugs).

Complexity

  • Time: O(b^(d/2)) expansions; for Word Ladder concretely O(N · L²) with buckets
  • Space: O(b^(d/2)) — this is bidirectional’s own cost: the backward frontier must fit in memory (IDA* + pruning tables, lab-01/02, is the escape when it doesn’t)

Implementation Requirements

  • Swap to expand the smaller frontier every level — without this, worst case reverts toward b^d
  • Meet check against the opposite frontier before the visited check
  • Level counter incremented once per level, not per node
  • end not in words short-circuit before building anything
  • For directed graphs: backward expansion must use reversed edges — verify invertibility before choosing this technique

Tests

  • The classic hit→cog example → 5
  • endWord missing from dictionary → 0
  • begin == end handling per problem statement
  • Length-1 words (b=25 exactly)
  • No path exists but both components are large (disconnected) → 0, terminates when a frontier empties
  • Adversarial: 5000 words forming a dense cluster — compare node expansions vs one-directional (assert ~order-of-magnitude reduction)
  • Path of length 2 (begin and end adjacent) — meet on first expansion

Follow-up Questions

  • Why always expand the smaller frontier? → Total work is the sum of expanded frontier sizes; expanding the smaller side keeps both trees balanced at ~b^(d/2). Expanding a large side one extra level can cost more than the entire balanced search.
  • How do you return the actual path, not just the length? → Keep per-side parent dicts; on meeting at state m, splice parents(begin→m) + reversed parents(m→end). One shared visited set no longer suffices — you need to know which side owns each state.
  • When is bidirectional BFS not applicable? → Goal known only as a predicate (“any state where X”), non-invertible moves without a reverse-edge oracle, or many goal states (seed the backward frontier with all of them — fine if enumerable).
  • Does this work for weighted graphs? → Bidirectional Dijkstra exists but the stopping condition is subtle: you cannot stop at first meet; you stop when top_f + top_b ≥ best_meet_cost found so far. Getting this wrong is a classic bug.
  • Word Ladder II (all shortest paths, LC 126)? → Bidirectional BFS to build a DAG of parents level-by-level, then DFS the DAG to emit paths. Deduplicate per level, not globally.
  • How does Kociemba’s solver relate? → Same halving principle, but the backward half is precomputed offline into pruning tables (exact distances in a quotient space), so the online search runs forward-only with a perfect-information heuristic. That trade — memory for a precomputed backward search — is the pattern behind all big puzzle solvers.

Product Extension

  • Social-graph degrees of separation (LinkedIn-style “3rd-degree connection” queries run bidirectionally)
  • Route planning seeds: bidirectional Dijkstra/ALT underlies road-network engines before contraction hierarchies
  • Diff/merge tooling: Myers diff explores an edit graph; bidirectional variants power git diff optimizations
  • Deadlock/reachability checking in model checkers (forward from init, backward from bad states)

Language/Runtime Follow-ups

  • Python: set operations are the hot path; frozenset swaps are cheap, string slicing for buckets is fine at L ≤ 10.
  • C++: unordered_set<string> hashing dominates — intern words to ints first for large dictionaries.
  • Java: HashSet<String>; watch autoboxing if interning to Integer.
  • JavaScript: Set + template strings; fine for LC constraints.

Common Bugs

  1. Meet check after visited check: neighbor already visited by the other side gets skipped and the meet is missed → returns longer path or 0.
  2. Forgetting to swap frontiers: still correct, but the complexity guarantee is gone; on skewed graphs it degrades to one-directional.
  3. Level counting off by one: returning edges instead of words (LC wants words) or incrementing per node instead of per level.
  4. Expanding into the visited set of the same side only: with two separate visited sets, a state may legitimately appear in both — that’s the meet, not a duplicate to skip.
  5. Backward expansion with forward edges on a directed graph: silently wrong distances; must use reverse adjacency.
  6. Mutating a frontier while iterating it: always build next_front fresh.

Debugging Strategy

  • Print (level, len(front), len(back)) per iteration — frontier sizes should stay balanced and small
  • Run one-directional BFS as oracle on small dictionaries; assert equal lengths over random instances
  • Test the directed-graph variant on a graph where forward and backward answers differ if edges aren’t reversed
  • Count node expansions bidirectional vs one-directional to confirm the ~√ speedup empirically

Mastery Criteria

  • Implement bucket-based bidirectional BFS for Word Ladder in ≤ 20 min, bug-free
  • State the two applicability conditions (explicit goal, invertible moves) unprompted
  • Explain the b^(d/2) math with a concrete number in ≤ 2 min
  • Know the bidirectional Dijkstra stopping-condition trap
  • Extend to path reconstruction in ≤ 10 additional min