Graph BFS

BFS finds the shortest path in an unweighted graph by exploring layer by layer. The invariant is that when a node is first visited, the shortest distance to it is known.

Pattern A: BFS in word graphs

Use when: you change one character at a time to reach a target.

Invariant: each BFS level represents one more transformation.

Skeleton:

queue = [begin]
visited = {begin}
steps = 1
while queue not empty:
    size = len(queue)
    repeat size times:
        word = pop
        if word == end: return steps
        for each neighbor in oneLetterVariants(word):
            if neighbor in dict and not visited:
                visited.add(neighbor)
                push neighbor
    steps++

Problems:

• word-ladder.

Pattern B: Multi-source BFS

Use when: multiple starting points spread simultaneously.

Invariant: all nodes in the queue at time t are exactly distance t from any source.

Skeleton:

queue = all sources
minutes = 0
while queue not empty:
    size = len(queue)
    repeat size times:
        node = pop
        for nei in neighbors:
            if fresh: mark; push
    if queue not empty: minutes++

Problems:

• rotting-oranges.

Pattern C: Grid shortest path

Use when: you need shortest path in a grid with obstacles.

Invariant: each cell is visited once at its shortest distance.

Skeleton:

queue = [(0,0,dist=1)]
visited[0][0] = true
while queue:
    r,c,d = pop
    if (r,c) == target: return d
    for dir in 8 directions:
        if valid and not visited: mark; push (nr,nc,d+1)

Problems:

• shortest-path-in-binary-matrix.

Pattern D: State-space BFS with mutation rules

Use when: nodes are strings and edges are single-step mutations.

Invariant: transitions are only to valid states in the bank/set.

Skeleton:

queue = [start]
visited = {start}
steps = 0
while queue:
    size = len(queue)
    repeat size times:
        cur = pop
        if cur == end: return steps
        for each mutation:
            if next in bank and not visited: push
    steps++

Problems:

• minimum-genetic-mutation.

Pattern E: Board BFS with jumps

Use when: you move by dice + ladder/snake jumps.

Invariant: nodes represent board indices after applying jumps.

Skeleton:

queue = [1]
visited = {1}
moves = 0
while queue:
    size = len(queue)
    repeat size times:
        cur = pop
        if cur == n*n: return moves
        for step in 1..6:
            next = cur + step
            next = jump(next) if ladder/snake
            if next not visited: push next
    moves++

Problems:

• snakes-and-ladders.

When to use Graph BFS (checklist)

• The graph is unweighted and you need shortest steps.
• The neighbor function is cheap or can be precomputed.

Common failures (checklist)

• Marking visited too late (causes duplicates).
• Forgetting to pre-validate start/end nodes.
• Treating weighted edges like unweighted BFS.

Problem mapping

• word-ladder: BFS over one-letter neighbors.
• snakes-and-ladders: BFS over board states.
• minimum-genetic-mutation: BFS over valid mutations.
• rotting-oranges: multi-source BFS.
• shortest-path-in-binary-matrix: BFS in 8 directions.