12 — Graph traversal

A graph is a set of things and a set of connections between them. Road networks, package dependencies, social follows, foreign keys between tables, the cells of a maze and the states of a puzzle are all graphs, and a large share of algorithm problems become routine once they are recognized as one. This chapter covers the vocabulary, the ways to store a graph, the two fundamental traversals (depth-first and breadth-first search), and the family of algorithms built directly on them: connected components, grid search, multi-source BFS, cycle detection, topological sort, union-find and bipartite checking. Weighted shortest paths, spanning trees, strongly connected components and the harder problems are in the next chapter.

Timings below were measured with Python 3.14 on one Mac. Exact numbers will differ elsewhere; the ratios are what matter. Every implementation shown was checked against a brute-force reference on hundreds of random small inputs.

Vocabulary

A graph $G = (V, E)$ has a set of vertices (or nodes) $V$ and a set of edges $E$. Throughout, $n = \lvert V \rvert$ and $m = \lvert E \rvert$. Complexity of graph algorithms is stated in both, because they vary independently: a graph with a million vertices can have a million edges or half a trillion.

Two counting facts come up constantly:

• Handshake lemma. In an undirected graph, $\sum_{v} \deg(v) = 2m$, because each edge contributes to two degrees. Iterating over every neighbor of every vertex in an adjacency list therefore costs $\Theta(n + m)$, not $\Theta(n \cdot \text{max degree})$.
• Edge bounds. A simple undirected graph has at most $n(n-1)/2$ edges, a simple digraph at most $n(n-1)$. So $m = O(n^2)$, and $\log m = O(\log n)$, which is why $O(m \log m)$ and $O(m \log n)$ are the same bound.

“Sparse” and “dense” are informal. A road network has an average degree of about 3 regardless of size, so $m = \Theta(n)$. A complete graph has $m = \Theta(n^2)$. Most real graphs, and nearly all interview graphs, are sparse, and that single fact decides the representation.

Representations

Three layouts cover almost every use.

Undirected graph            Adjacency matrix        Adjacency list     Edge list
                               0 1 2 3
  0 --- 1                   0 [0 1 1 0]             0: [1, 2]          (0, 1)
  |     |                   1 [1 0 0 1]             1: [0, 3]          (0, 2)
  2     3                   2 [1 0 0 0]             2: [0]             (1, 3)
                            3 [0 1 0 0]             3: [1]

Adjacency matrix. An $n \times n$ table, where entry $[u][v]$ is true (or holds the weight) when the edge exists. Edge lookup is one index operation. Listing a vertex’s neighbors scans a whole row, $\Theta(n)$, even if it has two neighbors. Memory is $\Theta(n^2)$ regardless of $m$.

Adjacency list. One list per vertex holding its neighbors (or (neighbor, weight) pairs). Memory is $\Theta(n + m)$. Listing neighbors costs $\Theta(\deg(v))$. Checking whether a specific edge exists costs $O(\deg(u))$ with a list, or expected $O(1)$ if each vertex’s neighbors are stored in a set instead.

Edge list. A flat list of (u, v) or (u, v, w) tuples. Memory is $\Theta(m)$, and it is the natural input format, but it answers neither “neighbors of v” nor “is (u, v) an edge” without a full scan. It is the right structure only when an algorithm processes edges as a batch, as Kruskal’s algorithm (sorted edges) and Bellman-Ford (relax every edge) do.

def to_adj_list(n, edges, directed=False):
    adj = [[] for _ in range(n)]
    for u, v in edges:
        adj[u].append(v)
        if not directed:
            adj[v].append(u)
    return adj

def to_matrix(n, edges, directed=False):
    m = [[False] * n for _ in range(n)]
    for u, v in edges:
        m[u][v] = True
        if not directed:
            m[v][u] = True
    return m

Note that [[False] * n] * n would create $n$ references to the same row, so setting one entry would set a whole column. The comprehension above creates distinct rows.

Measured on a sparse graph

A random undirected graph with 5,000 vertices and 20,000 edges (density 0.0016, average degree 8), built each way. Memory was measured with tracemalloc and counts the containers only; the integer objects are shared by all layouts.

The matrix uses 263 times the memory of the adjacency list, and a full traversal over it is 370 times slower, because it inspects all 25 million cells to find 40,000 neighbor entries. A list of Python lists spends 8 bytes on each cell (a pointer to the shared True or False object), so 5,000 squared cells cost 200 MB; a bytearray per row cuts that to 1 byte per cell but does not change the $\Theta(n^2)$ traversal cost. The adjacency list’s per-query cost is a linear scan of about 8 neighbors; with sets it matches the matrix.

Which to use

The last row is often the most important. A grid, a set of words or the states of a sliding puzzle are graphs whose edges follow from a rule, and generating neighbors in a function is cheaper than materializing them.

Depth-first search

The idea

DFS goes as deep as possible before backing up. From the current vertex it moves to any unvisited neighbor, and only when a vertex has no unvisited neighbors does it return to the vertex it came from. The “return to where I came from” step is a stack: either the call stack of a recursive function or an explicit list.

The invariant that makes DFS useful: a vertex is finished only after everything reachable from it through unvisited vertices has been finished. This is what lets DFS detect cycles, produce topological orders and find strongly connected components.

Recursive and iterative

def dfs_recursive(adj, start):
    order, seen = [], set()
    def visit(u):
        seen.add(u)
        order.append(u)
        for v in adj[u]:
            if v not in seen:
                visit(v)
    visit(start)
    return order

def dfs_iterative(adj, start):
    order, seen = [], set()
    stack = [start]
    while stack:
        u = stack.pop()
        if u in seen:
            continue
        seen.add(u)
        order.append(u)
        for v in reversed(adj[u]):   # reversed so neighbors pop in list order
            if v not in seen:
                stack.append(v)
    return order

On this graph:

  0 --- 1 --- 3
  |           |
  2 --- 4 --- 5

adjacency: [[1, 2], [0, 3], [0, 4], [1, 5], [2, 5], [3, 4]]
recursive DFS: [0, 1, 3, 5, 4, 2]
iterative DFS: [0, 1, 3, 5, 4, 2]

Two details in the iterative version matter.

Mark on pop, not on push. The iterative version above marks a vertex as seen when it is popped and skips stale stack entries. That reproduces the true depth-first order. A common variant marks vertices when they are pushed. It visits every reachable vertex exactly once and is fine for reachability and component counting, but its order is not a depth-first order, and it cannot produce correct finish times. Code that needs the DFS structure (cycle detection in digraphs, topological order, low-links) must use real DFS.

Stack size. Marking on pop can push a vertex several times, so the stack can hold up to $O(m)$ entries. The version that stores (vertex, iterator) frames, shown in the next section, keeps it to $O(n)$.

Python’s recursion limit

CPython’s default recursion limit is 1,000 frames. A DFS down a path of 100,000 vertices:

import sys
n = 100_000
path = [[i + 1] for i in range(n - 1)] + [[]]
print(sys.getrecursionlimit())
print(len(dfs_iterative(path, 0)))
try:
    dfs_recursive(path, 0)
except RecursionError as e:
    print("RecursionError:", e)

1000
100000
RecursionError: maximum recursion depth exceeded

sys.setrecursionlimit raises the limit, but deep native recursion can still exhaust the C stack and crash the interpreter rather than raise an exception. For graphs that can be deep (grids, long chains, anything from user input) the iterative form is the safe default. The recursive form is clearer for small or shallow graphs and for teaching the structure.

Discovery and finish times

Recording a counter when a vertex is first discovered and again when it is finished gives each vertex an interval $[d(u), f(u)]$. The iterative version keeps an iterator per stack frame so it can resume a vertex’s neighbor list exactly where it left off, which is what the recursive call stack does implicitly:

def dfs_times_iterative(adj):
    n = len(adj)
    disc, fin = [0] * n, [0] * n
    time = 0
    for s in range(n):
        if disc[s]:
            continue
        time += 1
        disc[s] = time
        stack = [(s, iter(adj[s]))]
        while stack:
            u, it = stack[-1]
            for v in it:
                if disc[v] == 0:
                    time += 1
                    disc[v] = time
                    stack.append((v, iter(adj[v])))
                    break
            else:
                stack.pop()
                time += 1
                fin[u] = time
    return disc, fin

The for ... else runs the else branch only when the iterator is exhausted without a break, which is exactly the moment the vertex finishes.

Parenthesis theorem. For any two vertices $u$ and $v$, their intervals are either disjoint or one is nested entirely inside the other; they never partially overlap. Nested means one is a descendant of the other in the DFS forest. This was checked on every random test graph.

White-path theorem. $v$ becomes a descendant of $u$ if and only if, at the moment $u$ is discovered, there is a path from $u$ to $v$ using only undiscovered vertices.

Edge classification

During DFS on a directed graph, every edge $(u, v)$ falls into one of four classes, decided by the state of $v$ when the edge is examined:

def dfs_times(adj):
    """Discovery/finish times and edge classes for a directed graph."""
    n = len(adj)
    disc, fin = [0] * n, [0] * n
    time = 0
    kinds = {}
    def visit(u):
        nonlocal time
        time += 1
        disc[u] = time
        for v in adj[u]:
            if disc[v] == 0:
                kinds[(u, v)] = "tree"
                visit(v)
            elif fin[v] == 0:
                kinds[(u, v)] = "back"
            elif disc[u] < disc[v]:
                kinds[(u, v)] = "forward"
            else:
                kinds[(u, v)] = "cross"
        time += 1
        fin[u] = time
    for s in range(n):
        if disc[s] == 0:
            visit(s)
    return disc, fin, kinds

On a digraph with edges 0→1, 0→2, 1→2, 2→0, 3→2, 3→4, 4→5, 5→3:

vertex  d  f            DFS forest
0       1  6            0            3
1       2  5            |            |
2       3  4            1            4
3       7  12           |            |
4       8  11           2            5
5       9  10

(0, 1) tree
(1, 2) tree
(2, 0) back
(0, 2) forward
(3, 2) cross
(3, 4) tree
(4, 5) tree
(5, 3) back

0→2 is forward because by the time vertex 0 examines it, 2 was already reached through 1 and finished. 3→2 is a cross edge into the first tree. The two back edges correspond to the two cycles, 0→1→2→0 and 3→4→5→3.

The key fact: a directed graph has a cycle if and only if DFS finds a back edge. In an undirected graph, DFS produces only tree edges and back edges; there are no forward or cross edges, because any edge to a finished vertex would have been traversed from that vertex’s side first.

Complexity

Each vertex is discovered once and each adjacency list is scanned once, so DFS with adjacency lists is $\Theta(n + m)$ time. With a matrix it is $\Theta(n^2)$. Extra space is $\Theta(n)$ for the visited marks plus the stack, which is $O(n)$ deep in the worst case (a path).

Breadth-first search

The idea

BFS explores in rings. It visits the source, then every vertex one edge away, then every vertex two edges away, and so on. A FIFO queue enforces the order: vertices are processed in the order they were discovered.

The invariant: the queue always holds vertices from at most two consecutive levels, $k$ and $k + 1$, with all level-$k$ vertices in front. It follows that vertices leave the queue in nondecreasing order of distance, and that is what makes BFS compute shortest paths in unweighted graphs.

from collections import deque

def bfs(adj, source):
    dist = [-1] * len(adj)
    parent = [-1] * len(adj)
    dist[source] = 0
    q = deque([source])
    while q:
        u = q.popleft()
        for v in adj[u]:
            if dist[v] == -1:
                dist[v] = dist[u] + 1
                parent[v] = u
                q.append(v)
    return dist, parent

def path_to(parent, target):
    path = []
    while target != -1:
        path.append(target)
        target = parent[target]
    return path[::-1]

On the six-vertex graph from the DFS section:

BFS distances: [0, 1, 1, 2, 2, 3]
path to 5: [0, 1, 3, 5]

level 0:   0
level 1:   1   2
level 2:   3   4
level 3:   5

The parent array forms the BFS tree: following parents from any reached vertex back to the source traces a shortest path.

Why BFS finds shortest paths

Let $\delta(v)$ be the true shortest distance from the source $s$, and $d(v)$ the label BFS assigns.

1. Labels are never too small. Every label $d(v) = d(u) + 1$ is assigned along an actual edge from a vertex with a valid label, so there is a real path of length $d(v)$ and $d(v) \ge \delta(v)$.
2. Labels are never too large. Suppose $\delta(v) = k$. Some neighbor $w$ of $v$ has $\delta(w) = k - 1$, and by induction $d(w) = k - 1$. Because vertices leave the queue in nondecreasing label order, $w$ is dequeued before any vertex labeled $k$ or more. When $w$ is processed, $v$ is either still unlabeled (and gets $k$) or already labeled by an earlier vertex with label at most $k - 1$, giving at most $k$. So $d(v) \le k$.

The argument depends on every edge having the same length. With weights, a two-edge path can be shorter than a one-edge path, so the first discovery is no longer the best one, and BFS gives wrong answers; Dijkstra’s algorithm or, for weights of only 0 and 1, 0-1 BFS replaces it (chapter 13).

Pitfalls

• Mark when enqueued, not when dequeued. If a vertex is marked only when it is taken off the queue, it can be added many times by different neighbors before then. Distances stay correct, but the queue can grow to $O(m)$ and work is repeated. In grids this can be the difference between passing and timing out.
• Use collections.deque. list.pop(0) shifts every remaining element and costs $O(n)$, which turns BFS quadratic.
• Level-by-level processing. When the answer is “number of rounds” (minutes, moves, generations), process the queue in batches of len(q) and count batches, or store the distance with each vertex. Rotting Oranges below does the former.
• Unreachable vertices keep their sentinel (-1 here). Callers must check it rather than assume connectivity.

Complexity

$\Theta(n + m)$ time with adjacency lists, $\Theta(n)$ extra space. The queue can hold an entire level at once, which for a wide graph (a star, or the frontier of a large grid) is $\Theta(n)$. DFS on the same graph may use far less memory if the graph is wide and shallow, and far more if it is narrow and deep.

DFS or BFS?

DFS and BFS on 2D grids

A grid is a graph whose vertices are cells (r, c) and whose edges connect adjacent passable cells. Nothing needs to be built: neighbors are computed from offsets.

DIRS4 = ((1, 0), (-1, 0), (0, 1), (0, -1))
DIRS8 = DIRS4 + ((1, 1), (1, -1), (-1, 1), (-1, -1))

4-directional          8-directional
    . N .                  NW N NE
    W x E                  W  x  E
    . S .                  SW S SE

4-directional movement is the default for “adjacent” (rook-like, Manhattan distance). 8-directional includes diagonals (king-like, Chebyshev distance). The choice changes answers: two cells touching only at a corner are separate islands under 4-connectivity and one island under 8-connectivity. Problems usually state which; “horizontally or vertically” means 4.

A grid with $R$ rows and $C$ columns has $n = RC$ vertices and at most $2RC$ edges with 4 directions (about $4RC$ with 8), so traversal is $\Theta(RC)$.

Boundary handling

Every neighbor must be checked against the grid edges before it is read. Python makes this easy to get subtly wrong: grid[-1][c] does not raise, it silently reads the last row. Three standard approaches:

1. Explicit check 0 <= nr < rows and 0 <= nc < cols before indexing. Clear and the usual choice.
2. Sentinel padding. Surround the grid with a border of blocked cells so that no in-grid cell has an out-of-range neighbor. The check disappears from the inner loop. Flattening to a 1D array with row stride $C + 2$ makes neighbor offsets the constants $\pm 1$ and $\pm (C + 2)$.
3. Dictionary or set of passable cells, where (r, c) in cells is false outside the grid. Natural for sparse or irregular boards and for infinite grids.

Marking visited cells

A separate seen set of tuples is general but allocates a tuple and hashes it for every cell. When the grid may be modified, overwriting a visited cell (land becomes water, fresh becomes rotten) uses the grid itself as the visited set. Number of Islands on a 1000 by 1000 random grid with 55% land (43,836 islands), best of three runs:

In-place marking halves the time. Padding and flattening take it to a third, including the cost of building the padded copy. If the caller’s grid must not change, copy it first; the copy is still cheaper than the set. If the grid is shared or reused, mutating it is a bug, so the choice is a contract decision, not only a speed one.

Number of Islands and connected components

Problem. Given a grid of '1' (land) and '0' (water), count the islands, where an island is a maximal 4-connected group of land cells.

This is “count the connected components” on an implicit graph. Scan every cell; each unvisited land cell starts a new component, and a traversal from it marks the whole component.

def num_islands(grid):
    """grid: list of lists of '1'/'0'. Modifies grid in place."""
    rows, cols = len(grid), len(grid[0]) if grid else 0
    count = 0
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] != "1":
                continue
            count += 1
            grid[r][c] = "0"
            stack = [(r, c)]
            while stack:
                y, x = stack.pop()
                for dy, dx in DIRS4:
                    ny, nx = y + dy, x + dx
                    if 0 <= ny < rows and 0 <= nx < cols and grid[ny][nx] == "1":
                        grid[ny][nx] = "0"
                        stack.append((ny, nx))
    return count

11000
11000      ->  3 islands
00100
00011

The stack-based traversal marks on push, which is fine here: only the set of reached cells matters, not the order. Time $\Theta(RC)$; extra space is the stack, $O(RC)$ in the worst case (a grid that is all land).

The same scan-and-traverse pattern counts components in any graph: loop over all vertices, and start a DFS or BFS from each unvisited one. Union-find (below) gives a third method, and it is the right one when edges arrive over time (Number of Islands II, where land is added cell by cell and the count is needed after each addition).

Variants of this problem are solved by changing what the traversal accumulates: Max Area of Island counts cells per component; Surrounded Regions and Number of Enclaves start traversals from the border cells to find which regions touch the edge; Pacific Atlantic Water Flow runs two traversals backward from each ocean’s border and intersects the results.

Flood fill

Flood fill is the operation behind a paint program’s bucket tool: starting at one cell, recolor it and every cell connected to it through cells of the same original color. It is a connected-component traversal that stops at a color boundary.

def flood_fill(image, sr, sc, color):
    old = image[sr][sc]
    if old == color:
        return image
    rows, cols = len(image), len(image[0])
    image[sr][sc] = color
    q = deque([(sr, sc)])
    while q:
        r, c = q.popleft()
        for dr, dc in DIRS4:
            nr, nc = r + dr, c + dc
            if 0 <= nr < rows and 0 <= nc < cols and image[nr][nc] == old:
                image[nr][nc] = color
                q.append((nr, nc))
    return image

The early return when old == color is essential, not an optimization. Without it, a recolored cell still matches old, so it is re-enqueued forever (or, in the recursive form, recurses without end). The new color doubles as the visited mark only because it differs from the old one.

The textbook recursive form, fill(r, c) calling itself on four neighbors, hits the recursion limit on any region larger than about a thousand cells. Graphics libraries use a scanline variant that fills a whole horizontal run at once and pushes only one seed per run in the rows above and below, which greatly reduces stack traffic. All forms are $\Theta(\text{region size})$.

Implicit and infinite grids

Some grids have no edge: a chess knight on an unbounded board, a robot on the integer plane, the reachable states of a puzzle. The graph is infinite, so the visited structure must be a hash set of coordinates, and termination comes from BFS reaching the target, not from exhausting the graph.

Minimum Knight Moves. Find the fewest knight moves from (0, 0) to (x, y) on an infinite board.

def knight_distance(tx, ty):
    """Minimum knight moves from (0,0) to (tx,ty) on an infinite board."""
    tx, ty = abs(tx), abs(ty)
    moves = ((1, 2), (2, 1), (-1, 2), (-2, 1), (1, -2), (2, -1), (-1, -2), (-2, -1))
    seen = {(0, 0)}
    q = deque([(0, 0, 0)])
    while q:
        x, y, d = q.popleft()
        if (x, y) == (tx, ty):
            return d
        for dx, dy in moves:
            nx, ny = x + dx, y + dy
            if (nx, ny) not in seen and -2 <= nx <= tx + 2 and -2 <= ny <= ty + 2:
                seen.add((nx, ny))
                q.append((nx, ny, d + 1))

print(knight_distance(2, 1), knight_distance(5, 5), knight_distance(1, 1), knight_distance(300, 0))

1 4 2 150

Two ideas keep it finite and fast. Symmetry folds the target into the first quadrant. A bounding box a little larger than the rectangle between origin and target prunes the search: some optimal paths step slightly outside the rectangle (reaching (1, 1) takes two moves, both through negative coordinates or beyond the target), which is why the box extends by 2. The bound was verified by comparing against an unpruned BFS on a 61 by 61 board for every target with coordinates from -8 to 8. Without some bound, BFS explores a disk whose area grows with the square of the distance.

Further techniques for large implicit graphs:

• Bidirectional BFS grows a frontier from both ends and stops when they meet. If each frontier grows by a factor $b$ per level and the answer is $d$, the work drops from roughly $b^d$ to $2b^{d/2}$.
• Encoding states compactly (a tuple, a string, or an integer bitmask) so they can be hashed into the visited set. Open the Lock and Sliding Puzzle are BFS over state strings.
• A* search adds a heuristic to steer toward the target (chapter 13).

Multi-source BFS

The idea

Some problems ask for each cell’s distance to the nearest of many sources. Running a BFS from every source costs $\Theta(k \cdot n)$ for $k$ sources. Multi-source BFS starts with all sources in the queue at distance 0 and runs a single BFS. The result is exact, by the same argument as ordinary BFS applied to an imagined super-source joined by an edge to every real source: distance from the super-source minus one equals distance to the nearest real source. The cost is $\Theta(n + m)$ regardless of $k$.

Walls and Gates

Problem. In a grid, -1 is a wall, 0 is a gate and INF (2,147,483,647) is an empty room. Fill each room with its distance to the nearest gate, leaving INF if no gate is reachable.

INF = 2**31 - 1

def walls_and_gates(rooms):
    rows, cols = len(rooms), len(rooms[0]) if rooms else 0
    q = deque((r, c) for r in range(rows) for c in range(cols) if rooms[r][c] == 0)
    while q:
        r, c = q.popleft()
        for dr, dc in DIRS4:
            nr, nc = r + dr, c + dc
            if 0 <= nr < rows and 0 <= nc < cols and rooms[nr][nc] == INF:
                rooms[nr][nc] = rooms[r][c] + 1
                q.append((nr, nc))

before                      after
INF  -1   0 INF               3  -1   0   1
INF INF INF  -1               2   2   1  -1
INF  -1 INF  -1               1  -1   2  -1
  0  -1 INF INF               0  -1   3   4

The check rooms[nr][nc] == INF is both the passability test and the visited test: once a room gets a distance it is never revisited, and the first distance it gets is the smallest, because the BFS frontiers from all gates advance in lockstep.

On a 200 by 200 grid with 20% walls, the single multi-source BFS took about 10 ms whatever the number of gates. One BFS per gate took about 168 ms with 10 gates, 1.6 s with 100 gates, and 7 s with 400 gates.

Rotting Oranges

Problem. Cells are empty (0), fresh (1) or rotten (2). Each minute, every fresh orange adjacent to a rotten one becomes rotten. Return the minutes until no fresh orange remains, or -1 if some never rot.

The rotten oranges are the sources. Processing the queue one level at a time counts minutes.

def oranges_rotting(grid):
    rows, cols = len(grid), len(grid[0])
    q = deque()
    fresh = 0
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == 2:
                q.append((r, c))
            elif grid[r][c] == 1:
                fresh += 1
    minutes = 0
    while q and fresh:
        for _ in range(len(q)):
            r, c = q.popleft()
            for dr, dc in DIRS4:
                nr, nc = r + dr, c + dc
                if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 1:
                    grid[nr][nc] = 2
                    fresh -= 1
                    q.append((nr, nc))
        minutes += 1
    return -1 if fresh else minutes

print(oranges_rotting([[2, 1, 1], [1, 1, 0], [0, 1, 1]]))
print(oranges_rotting([[2, 1, 1], [0, 1, 1], [1, 0, 1]]))
print(oranges_rotting([[0, 2]]))

4
-1
0

In the second grid the bottom-left orange is cut off from every rotten one; in the third there is nothing fresh to begin with.

The loop condition while q and fresh handles the edge cases: no fresh oranges gives 0 without counting an empty final round, and fresh oranges with no rotten source give -1. The counter fresh avoids a final rescan of the grid. The function was checked against a direct minute-by-minute simulation on 500 random grids.

Other multi-source BFS problems: 01 Matrix (distance from each cell to the nearest 0), As Far from Land as Possible (the water cell maximizing distance to land), Shortest Bridge (BFS outward from every cell of one island until reaching the other), and Map of Highest Peak.

Word Ladder

Problem. Given beginWord, endWord and a word list, find the number of words in the shortest transformation sequence where each step changes exactly one letter and every intermediate word is in the list. Return 0 if none exists.

The words are vertices, and two words are adjacent when they differ in exactly one position. The question is a shortest path in an unweighted graph, so BFS. The difficulty is generating neighbors efficiently. Three methods, for $N$ words of length $L$:

The bucket version precomputes, for every word and every position, a pattern with that position replaced by *. Words sharing a pattern are neighbors.

from collections import defaultdict, deque

def ladder_length(begin, end, words):
    words = set(words)
    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)
    seen = {begin}
    q = deque([(begin, 1)])
    while q:
        w, d = q.popleft()
        if w == end:
            return d
        for i in range(len(w)):
            key = w[:i] + "*" + w[i + 1:]
            for nxt in buckets[key]:
                if nxt not in seen:
                    seen.add(nxt)
                    q.append((nxt, d + 1))
            buckets[key] = []          # each bucket only needs expanding once
    return 0

print(ladder_length("hit", "cog", ["hot", "dot", "dog", "lot", "log", "cog"]))
print(ladder_length("hit", "cog", ["hot", "dot", "dog", "lot", "log"]))

5
0

The first sequence is hit, hot, dot, dog, cog. The second fails because cog is not in the list.

Clearing a bucket after expanding it is safe because every word in the bucket has been marked seen with the current or a smaller distance; later visits to the same bucket could only rediscover them. Without the clear, a large bucket (common in small alphabets) is rescanned once per member, which is quadratic in the bucket size.

Measured on random 5-letter words over an 8-letter alphabet, including the time to build the buckets:

The pairwise method grows quadratically; the other two grow with the number of words actually expanded. Bidirectional BFS (expanding the smaller of two frontiers each round) is the standard further improvement. Word Ladder II, which asks for all shortest sequences, runs BFS to build a layered parent map and then backtracks through it; enumerating paths during the BFS itself blows up.

Clone Graph

Problem. Given a reference to a node in a connected undirected graph, where each node has a value and a list of neighbors, return a deep copy.

The traversal itself is routine. The point is the old-to-new map, which serves three purposes at once: it is the visited set, it ensures every original node gets exactly one copy, and it lets edges to already-copied nodes be wired to the existing copy instead of a duplicate.

class Node:
    def __init__(self, val, neighbors=None):
        self.val = val
        self.neighbors = neighbors if neighbors is not None else []

def clone_graph(node):
    if node is None:
        return None
    copies = {node: Node(node.val)}
    q = deque([node])
    while q:
        cur = q.popleft()
        for nb in cur.neighbors:
            if nb not in copies:
                copies[nb] = Node(nb.val)
                q.append(nb)
            copies[cur].neighbors.append(copies[nb])
    return copies[node]

The copy is created when a node is first discovered, not when it is dequeued, so that an edge to a node still waiting in the queue can be wired immediately. Keying the map by node object rather than by value is what makes this correct when values repeat. Time and space are $\Theta(n + m)$. The same pattern copies any pointer structure with sharing or cycles: Copy List with Random Pointer is the linked-list version. Python’s copy.deepcopy uses the same idea internally, with a memo dictionary keyed by object id.

The tests walked the original and the clone in lockstep, checking that values and neighbor counts match, that the same original always maps to the same copy, and that no copy is an original node.

Cycle detection

Undirected graphs

DFS with a parent check. In an undirected DFS, every edge to an already-visited vertex is a back edge, which closes a cycle, except the edge just used to arrive. So DFS reports a cycle when it meets a visited neighbor that is not the vertex it came from.

The usual formulation checks v != parent. That is wrong on multigraphs: two parallel edges between u and v form a cycle of length 2, but the check skips both. Tracking the edge used to arrive, rather than the parent vertex, handles parallel edges correctly:

def has_cycle_undirected(n, edges):
    adj = [[] for _ in range(n)]
    for i, (u, v) in enumerate(edges):
        adj[u].append((v, i))
        adj[v].append((u, i))
    seen = [False] * n
    for s in range(n):
        if seen[s]:
            continue
        seen[s] = True
        stack = [(s, -1)]               # (vertex, id of edge used to reach it)
        while stack:
            u, via = stack.pop()
            for v, eid in adj[u]:
                if eid == via:
                    continue
                if seen[v]:
                    return True
                seen[v] = True
                stack.append((v, eid))
    return False

This version marks on push. Any visited vertex reached through an edge other than the arrival edge means two distinct routes from the start of the component reach it, and two distinct routes form a cycle; it does not need true DFS order. A self-loop (u, u) is reported as a cycle, as it should be.

print(has_cycle_undirected(4, [(0, 1), (1, 2), (2, 3)]), has_cycle_undirected(4, [(0, 1), (1, 2), (2, 0)]))
print(has_cycle_undirected(2, [(0, 1), (0, 1)]), has_cycle_uf(2, [(0, 1), (0, 1)]))

False True
True True

A path has no cycle, a triangle does, and two parallel edges between the same pair count as a cycle under both methods.

There is also a counting shortcut: a graph with $c$ components is a forest exactly when $m = n - c$. The tests used it as the reference.

Union-find. Process edges one at a time. If both endpoints are already in the same set, the new edge closes a cycle; otherwise merge their sets.

def has_cycle_uf(n, edges):
    d = DSU(n)
    return any(not d.union(u, v) for u, v in edges)

DSU is defined in the union-find section below. This is the natural choice when edges arrive as a stream, and it is the test Kruskal’s algorithm uses to reject edges. It also answers Redundant Connection directly: the first edge whose endpoints are already connected is the answer.

Directed graphs: three-color DFS

In a digraph, reaching an already-visited vertex does not imply a cycle. In the diamond 0→1, 0→2, 1→3, 2→3, vertex 3 is reached twice but there is no cycle. What matters is whether the visited vertex is on the current DFS path, which is precisely a back edge. Three colors track it:

• White: undiscovered.
• Gray: discovered, still on the stack (its descendants are being explored).
• Black: finished.

An edge to a gray vertex is a back edge, so a cycle.

WHITE, GRAY, BLACK = 0, 1, 2

def has_cycle_directed(adj):
    color = [WHITE] * len(adj)
    for s in range(len(adj)):
        if color[s] != WHITE:
            continue
        color[s] = GRAY
        stack = [(s, iter(adj[s]))]
        while stack:
            u, it = stack[-1]
            for v in it:
                if color[v] == GRAY:
                    return True
                if color[v] == WHITE:
                    color[v] = GRAY
                    stack.append((v, iter(adj[v])))
                    break
            else:
                color[u] = BLACK
                stack.pop()
    return False

print(has_cycle_directed([[1], [2], []]), has_cycle_directed([[1], [2], [0]]))
print(has_cycle_directed([[1, 2], [3], [3], []]))     # the diamond

False True
False

This version must be genuine DFS (the iterator-frame form, or recursion). Marking on push loses the “currently on the path” information. Kahn’s algorithm in the next section is an alternative that needs no DFS at all. To report the cycle rather than just detect it, keep a parent pointer and, on finding the back edge u→v, walk parents from u back to v.

Time is $\Theta(n + m)$ for all three methods (union-find is $O(m\,\alpha(n))$, effectively the same).

Topological sort

The problem

A topological order of a directed graph lists the vertices so that every edge $u \to v$ has $u$ before $v$. It exists if and only if the graph is a DAG: a cycle needs some edge to point backward in any order, and every DAG has at least one vertex with in-degree 0 to start with (otherwise walking backward along incoming edges would eventually repeat a vertex, forming a cycle). Build systems, package managers, spreadsheet recalculation, course prerequisites and the migration order of PostgreSQL tables linked by foreign keys are all topological sorts.

A DAG usually has many valid orders. The order is unique exactly when consecutive vertices in it are all joined by edges, that is, when the DAG has a Hamiltonian path.

Kahn’s algorithm (BFS on in-degrees)

Repeatedly output a vertex with no remaining incoming edges, and delete its outgoing edges. Arthur Kahn published this in 1962.

def topo_kahn(n, edges):
    adj = [[] for _ in range(n)]
    indeg = [0] * n
    for u, v in edges:
        adj[u].append(v)
        indeg[v] += 1
    q = deque(u for u in range(n) if indeg[u] == 0)
    order = []
    while q:
        u = q.popleft()
        order.append(u)
        for v in adj[u]:
            indeg[v] -= 1
            if indeg[v] == 0:
                q.append(v)
    return order if len(order) == n else None      # None: there is a cycle

Walking through edges 0→1, 0→2, 1→3, 2→3, 3→4:

in-degrees    queue     output
0:0 1:1 2:1 3:2 4:1
              [0]
pop 0  -> 1:0 2:0       [1, 2]    0
pop 1  -> 3:1           [2]       0 1
pop 2  -> 3:0           [3]       0 1 2
pop 3  -> 4:0           [4]       0 1 2 3
pop 4                   []        0 1 2 3 4

Cycle detection comes free. Vertices on a cycle (and everything downstream of one) never reach in-degree 0, so if fewer than $n$ vertices are output, the graph has a cycle, and the unprocessed vertices with nonzero in-degree contain it.

Useful variations:

• Replacing the queue with a min-heap produces the lexicographically smallest topological order, at $O(m + n \log n)$.
• If the queue ever holds two or more vertices, the order is not unique (Sequence Reconstruction asks exactly this).
• Processing the queue in rounds gives the minimum number of parallel stages (Parallel Courses): the round count is the length of the longest path, in vertices.

DFS post-order

In DFS, a vertex finishes only after every vertex reachable from it has finished. So for every edge $u \to v$ in a DAG, $f(v) < f(u)$: if $v$ was white when the edge was examined, it is a descendant and finishes first; if black, it already finished; gray is impossible, because that would be a back edge and a cycle. Sorting by decreasing finish time, which is reversing the post-order, is therefore a topological order.

def topo_dfs(n, edges):
    adj = [[] for _ in range(n)]
    for u, v in edges:
        adj[u].append(v)
    color = [WHITE] * n
    post = []
    for s in range(n):
        if color[s] != WHITE:
            continue
        color[s] = GRAY
        stack = [(s, iter(adj[s]))]
        while stack:
            u, it = stack[-1]
            for v in it:
                if color[v] == GRAY:
                    return None
                if color[v] == WHITE:
                    color[v] = GRAY
                    stack.append((v, iter(adj[v])))
                    break
            else:
                color[u] = BLACK
                post.append(u)
                stack.pop()
    return post[::-1]

edges = [(0, 1), (0, 2), (1, 3), (2, 3), (3, 4)]
print(topo_kahn(5, edges), topo_dfs(5, edges))
print(topo_kahn(3, [(0, 1), (1, 2), (2, 0)]), topo_dfs(3, [(0, 1), (1, 2), (2, 0)]))

[0, 1, 2, 3, 4] [0, 2, 1, 3, 4]
None None

Both orders are valid; they differ because the methods break ties differently. The tests checked on random digraphs that each output is a permutation in which every edge points forward, and that both return None exactly when a transitive-closure brute force finds a cycle.

A frequent bug is reversing the wrong thing: the preorder (discovery order) reversed is not a topological order, and the post-order unreversed is a valid order for the reversed graph. In the recursive form, appending u after the loop over its neighbors is the post-order.

Course Schedule

Course Schedule (I). Given numCourses and pairs [a, b] meaning “take b before a”, decide whether all courses can be finished. That is “is the prerequisite graph acyclic?”.

def can_finish(num_courses, prerequisites):
    # [a, b] means "take b before a", so the edge is b -> a
    return topo_kahn(num_courses, [(b, a) for a, b in prerequisites]) is not None

print(can_finish(2, [[1, 0]]), can_finish(2, [[1, 0], [0, 1]]))

True False

Course Schedule II asks for the order itself and is topo_kahn returning the list (or an empty list for None). The most common mistake in both is the edge direction; getting it backward produces the reverse order for II and, for I, still the right yes/no answer, which hides the bug until II. Alien Dictionary is a topological sort whose edges come from the first differing letter of each adjacent pair of sorted words, with the extra trap that a word followed by its own proper prefix is an invalid input.

Union-find (disjoint set union)

The problem it solves

Union-find maintains a partition of $n$ elements into disjoint sets under two operations:

• find(x): return a representative of the set containing $x$. Two elements are in the same set exactly when their representatives are equal.
• union(a, b): merge the sets containing $a$ and $b$.

It answers “are these connected?” as edges are added, in nearly constant time per operation. It cannot split sets or delete edges; for that, a graph traversal must be rerun (or an offline technique used).

Representation and invariant

Each set is a rooted tree stored in a parent array; a root is its own parent and serves as the representative. find walks up to the root; union points one root at the other.

parent: [0, 0, 1, 3, 3, 4]

    0        3
    |       / \
    1      4   (3 is its own parent)
    |      |
    2      5          find(2) = 0, find(5) = 3

Without any balancing, a sequence of unions can build a chain of height $n - 1$, and find on the bottom element walks all of it. Two independent optimizations fix this.

Union by size (or by rank). Always attach the root of the smaller tree under the root of the larger. An element’s depth increases only when its tree is merged into one at least as large, so its tree at least doubles each time its depth grows; the depth is therefore at most $\log_2 n$. Union by rank uses an upper bound on height instead of size, with the same $O(\log n)$ guarantee. Size has the practical advantage of also answering “how big is this component?”.

Path compression. During find, after locating the root, point every vertex on the walked path directly at the root. Later finds on any of them take one step.

class DSU:
    def __init__(self, n):
        self.parent = list(range(n))
        self.size = [1] * n
        self.components = n

    def find(self, x):
        root = x
        while self.parent[root] != root:
            root = self.parent[root]
        while self.parent[x] != root:          # path compression
            self.parent[x], x = root, self.parent[x]
        return root

    def union(self, a, b):
        ra, rb = self.find(a), self.find(b)
        if ra == rb:
            return False
        if self.size[ra] < self.size[rb]:      # union by size
            ra, rb = rb, ra
        self.parent[rb] = ra
        self.size[ra] += self.size[rb]
        self.components -= 1
        return True

find is written as two loops rather than recursively so that a long chain cannot hit the recursion limit. The tuple assignment self.parent[x], x = root, self.parent[x] evaluates the right side first, so x moves to its old parent after the old link is replaced. union returning False when the elements were already joined is what the cycle check and Kruskal’s algorithm use, and components gives the component count at any moment.

The bound

With both optimizations, any sequence of $m$ operations on $n$ elements takes $O(m\,\alpha(n))$ time, where $\alpha$ is the inverse Ackermann function. Robert Tarjan proved this upper bound in 1975, and later lower-bound results, including Fredman and Saks (1989), showed that no structure of this kind can do asymptotically better. $\alpha(n)$ grows so slowly that it is at most 4 for any $n$ that could be written down in the physical universe, so in practice the operations are constant time. The bound is amortized: an individual find can still take $O(\log n)$ steps, but compression makes repeated long walks impossible.

Each optimization alone also gives a logarithmic bound: union by size alone guarantees $O(\log n)$ worst case per find; path compression alone gives $O(\log n)$ amortized per operation (Tarjan and van Leeuwen, 1984). It is commonly said that union-find is “O(1)”; it is $O(\alpha(n))$ amortized, which is not constant but is indistinguishable from it.

Measured effect of each optimization

Two workloads, best of three runs each. “Parent hops/op” counts the steps find takes walking up to the root, averaged over all operations; “final height” is the deepest tree afterward.

Chain-building, $n = 5{,}000$: union(i, 0) then find(0) for each $i$. Without balancing, each union hangs the existing tree under a new singleton, so the tree is a path and element 0 sits at the bottom.

Random, $n = 50{,}000$: 50,000 unions of random pairs, each followed by a find on a random element.

The unoptimized version is hundreds of times slower on both workloads. The chain case shows that compression alone can leave a tree of height 4,998 and still be fast: the repeated finds on element 0 keep compressing the one path that matters, but a find on some other deep element would still pay a long walk once. Union by size alone does surprisingly well on both workloads; combining it with compression mainly protects against adversarial access patterns and keeps the final trees flatter. In Python, where each loop iteration is expensive, both together is the standard choice and costs nothing extra.

Uses

• Connected components with edges arriving over time (Number of Islands II, Number of Provinces, the online form of any component count).
• Cycle detection in undirected graphs and Redundant Connection.
• Kruskal’s minimum spanning tree (chapter 13).
• Grouping by equivalence: Accounts Merge (union accounts sharing an email), Satisfiability of Equality Equations (union all a==b, then check every a!=b lands in different sets), Similar String Groups.
• Offline connectivity: when queries can be reordered, processing them sorted by a threshold and adding edges in that order turns “connected using only edges below weight w?” into union-find.

Bipartite check

The problem

A graph is bipartite if its vertices can be split into two sides with every edge crossing between the sides. Equivalently, it can be colored with two colors so that no edge joins same-colored vertices. The classical characterization (due to Dénes Kőnig): a graph is bipartite if and only if it has no cycle of odd length. A cycle alternates sides with each edge, so it returns to its starting side only after an even number of steps.

BFS coloring

Color the start vertex 0. Every neighbor of a color-0 vertex must be color 1, and vice versa. BFS propagates the forced colors; meeting an edge whose endpoints already have the same color proves an odd cycle. Each component is colored independently, because the graph may be disconnected.

def is_bipartite(adj):
    color = [-1] * len(adj)
    for s in range(len(adj)):
        if color[s] != -1:
            continue
        color[s] = 0
        q = deque([s])
        while q:
            u = q.popleft()
            for v in adj[u]:
                if color[v] == -1:
                    color[v] = 1 - color[u]
                    q.append(v)
                elif color[v] == color[u]:
                    return False
    return True

print(is_bipartite(to_adj_list(4, [(0, 1), (1, 2), (2, 3), (3, 0)])))
print(is_bipartite(to_adj_list(3, [(0, 1), (1, 2), (2, 0)])))

True
False

The square splits into sides {0, 2} and {1, 3}; the triangle is an odd cycle.

The coloring is forced, not chosen: once one vertex in a component is fixed, every other vertex’s color is determined by the parity of its BFS distance. That is why a single conflict proves the graph is not bipartite, with no backtracking needed. With BFS, a conflict edge joins two vertices at the same level (an edge can only join equal or adjacent levels), and their paths back to the common ancestor plus the edge form an odd cycle.

The tests compared against trying all $2^n$ colorings on small random graphs, including graphs with self-loops (never bipartite) and disconnected graphs (the outer loop is required; forgetting it is the classic bug in Is Graph Bipartite?). Time is $\Theta(n + m)$.

DFS coloring works the same way. Union-find also works: for each vertex, union all of its neighbors together, and report failure if any neighbor ends up in the vertex’s own set.

Problems: Is Graph Bipartite?, Possible Bipartition (people who dislike each other must be in different groups; build the dislike graph and check it). Two-coloring is the only coloring problem solvable this way: deciding whether a graph can be 3-colored is NP-complete (chapter 13 covers general coloring).

Pitfalls across graph problems

Summary