Graph Algorithms

Chapter 1: Breadth-First Search

Imagine you drop a stone in a pond. Ripples spread outward in concentric rings — first the point of impact, then one meter out, then two meters, then three. Breadth-First Search (BFS) explores a graph exactly like those ripples. Starting from a source vertex s, it discovers all vertices at distance 1 first, then all at distance 2, then distance 3, and so on. It never jumps ahead. It is the most patient algorithm in graph theory.

The Coloring Scheme

CLRS uses three colors to track vertex states during BFS. This is not just notation — the colors correspond to a fundamental invariant that makes BFS correct.

White: undiscovered. The vertex has not been seen at all. Every vertex starts white.

Gray: discovered but not finished. The vertex is in the queue. We know it exists, but we have not yet explored all of its neighbors. Gray vertices form the "frontier" — the wavefront of the ripple.

Black: finished. We have dequeued this vertex and explored all of its neighbors. Every neighbor of a black vertex has been discovered (is gray or black). Black vertices are behind the wavefront.

The Algorithm

Every vertex is enqueued at most once (when it turns gray) and dequeued at most once (when it turns black). Every edge is examined at most once (when its source vertex is dequeued and we scan its adjacency list). The V initialization loop contributes O(V). The total work across all dequeue operations is ∑ degree(u) = 2|E| for undirected (|E| for directed). Total runtime: O(V + E).

Space: O(V) for the queue, color array, distance array, and parent array. In the worst case (star graph — source has V-1 neighbors), all V-1 vertices enter the queue simultaneously. But we never need more than O(V) space total.

Worked Example

Consider a graph with vertices {A, B, C, D, E, F} and edges A→B, A→C, B→D, C→D, C→E, D→F. Let the source be A.

BFS tree (parent pointers): B←A, C←A, D←B, E←C, F←D. The shortest path from A to F is A → B → D → F (length 3).

The BFS Tree

The parent pointers π[v] define a BFS tree (or BFS forest if the graph is disconnected). The BFS tree has a remarkable property: every tree edge connects a vertex at distance d to a vertex at distance d+1. There are no "shortcuts" — the tree faithfully represents the shortest-path structure.

For an undirected graph, every non-tree edge connects vertices at the same distance or adjacent distances (|d[u] - d[v]| ≤ 1). This is because if |d[u] - d[v]| ≥ 2, then BFS would have discovered the closer vertex through the farther one, making this a tree edge.

Step Through BFS

The simulation below runs BFS on a sample graph. Each step dequeues one vertex, explores its neighbors, and colors them. Watch the queue (bottom) and the discovery distances update in real time.

Implementation

python
from collections import deque

def bfs(graph, source):
    """BFS on adjacency-list graph. Returns (dist, parent) dicts."""
    color = {v: 'white' for v in graph}
    dist  = {v: float('inf') for v in graph}
    parent = {v: None for v in graph}

    color[source] = 'gray'
    dist[source]  = 0
    queue = deque([source])

    while queue:
        u = queue.popleft()
        for v in graph[u]:
            if color[v] == 'white':
                color[v]  = 'gray'
                dist[v]   = dist[u] + 1
                parent[v] = u
                queue.append(v)
        color[u] = 'black'

    return dist, parent

# Example
G = {
    'A': ['B', 'C'],
    'B': ['D'],
    'C': ['D', 'E'],
    'D': ['F'],
    'E': [],
    'F': []
}
dist, par = bfs(G, 'A')
# dist = {'A':0, 'B':1, 'C':1, 'D':2, 'E':2, 'F':3}

Why BFS Is Correct: The Proof Sketch

Let δ(s, v) denote the true shortest-path distance from s to v. We want to prove that d[v] = δ(s, v) for all v. The argument has three steps:

Step 1 (Upper bound): d[v] ≥ δ(s, v) always. BFS can only set d[v] = d[u] + 1 for some u, and by induction d[u] ≥ δ(s, u). Since δ(s, v) ≤ δ(s, u) + 1 (triangle inequality for unweighted graphs), we get d[v] ≥ δ(s, v).

Step 2 (Lower bound by contradiction): Suppose d[v] > δ(s, v) for some v. Pick the first such v in BFS order (smallest δ). Let u be v's predecessor on a true shortest path, so δ(s, v) = δ(s, u) + 1. Since δ(s, u) < δ(s, v), vertex u was correct: d[u] = δ(s, u). When u was dequeued, BFS examined edge (u, v). If v was white, BFS set d[v] = d[u] + 1 = δ(s, u) + 1 = δ(s, v). Contradiction. If v was already gray/black, then d[v] ≤ d[u] + 1 = δ(s, v). Also contradiction.

Step 3: Therefore d[v] = δ(s, v) for all reachable v. For unreachable v, d[v] remains ∞ = δ(s, v). QED.

BFS Properties Summarized (CLRS Theorems)

The eccentricity of a vertex s is max_v δ(s, v) — the maximum shortest-path distance from s to any other vertex. The diameter of a graph is the maximum eccentricity over all vertices: max_s max_v δ(s, v). Computing the diameter of a general graph requires BFS from every vertex: O(V(V + E)). For trees, two BFS passes suffice: BFS from any vertex, then BFS from the farthest vertex found. The farthest vertex from that second BFS is the diameter endpoint.

python
def tree_diameter(adj):
    """Diameter of an unweighted tree in 2 BFS passes."""
    def bfs_farthest(start):
        dist = {start: 0}
        queue = deque([start])
        farthest = start
        while queue:
            u = queue.popleft()
            for v in adj[u]:
                if v not in dist:
                    dist[v] = dist[u] + 1
                    queue.append(v)
                    if dist[v] > dist[farthest]:
                        farthest = v
        return farthest, dist[farthest]

    # Pass 1: find farthest from any vertex
    far1, _ = bfs_farthest(next(iter(adj)))
    # Pass 2: find farthest from that vertex = diameter
    far2, diameter = bfs_farthest(far1)
    return diameter

Multi-Source BFS

A powerful BFS variant: instead of starting from one source, start from multiple sources simultaneously. Add all sources to the queue at distance 0. BFS then finds the shortest distance from each vertex to its nearest source.

python
def multi_source_bfs(graph, sources):
    """BFS from multiple sources simultaneously.
    Returns dist[v] = min distance from v to any source."""
    dist = {v: float('inf') for v in graph}
    queue = deque()
    for s in sources:
        dist[s] = 0
        queue.append(s)
    while queue:
        u = queue.popleft()
        for v in graph[u]:
            if dist[v] == float('inf'):
                dist[v] = dist[u] + 1
                queue.append(v)
    return dist

# Use case: given a grid with multiple fire sources,
# find how long until fire reaches each cell.
# Use case: "01 Matrix" (LC 542) — distance to nearest 0.

Chapter 2: BFS Applications

BFS does more than find shortest paths. Its level-by-level exploration pattern makes it the right tool for several fundamental graph problems. Let us look at three.

Application 1: Connected Components (Undirected)

In an undirected graph, a connected component is a maximal set of vertices such that every pair is reachable from every other. "Maximal" means you cannot add any more vertices without breaking the reachability property.

To find all connected components, run BFS from an unvisited vertex. Everything BFS discovers is one component. Then find the next unvisited vertex and BFS again. Repeat until all vertices are visited.

Runtime: O(V + E) total — each vertex and edge is processed exactly once across all BFS calls.

Application 2: Bipartiteness Testing

A graph is bipartite if you can color every vertex with one of two colors (say red and blue) such that no edge connects two vertices of the same color. Think: assigning students to two exam rooms so that no pair of friends is in the same room. Or: can you divide a class into two teams for a debate, such that no pair of enemies is on the same team?

BFS naturally tests bipartiteness. During BFS, assign the source color 0. For each newly discovered vertex, assign the opposite color of its parent. If you ever encounter an already-colored neighbor with the same color as the current vertex, the graph is not bipartite.

Equivalently, a graph is bipartite if and only if it contains no odd-length cycle. This is because in a 2-coloring, traversing any edge switches the color. After an even number of edges, you return to the original color. After an odd number of edges, you are at the opposite color — and if this brings you back to the start vertex, you need both colors for the same vertex. Contradiction.

Worked Example: Bipartite Testing by Hand

Graph: A-B, A-D, B-C, C-D. Start BFS from A, color A=0.

Result: bipartite! Partition: {A, C} (color 0) and {B, D} (color 1). Cycle A-B-C-D-A has length 4 (even). No odd cycles.

Now add edge B-D: B (color=1) examines D (color=1) — same color! Not bipartite. The odd cycle is A-B-D-A (length 3).

python
from collections import deque

def is_bipartite(graph):
    """Returns True if undirected graph is bipartite."""
    color = {}
    for start in graph:
        if start in color:
            continue
        color[start] = 0
        queue = deque([start])
        while queue:
            u = queue.popleft()
            for v in graph[u]:
                if v not in color:
                    color[v] = 1 - color[u]  # opposite color
                    queue.append(v)
                elif color[v] == color[u]:
                    return False  # same-color neighbor!
    return True

Application 3: Connected Components (Full Implementation)

Finding connected components is one of the most common graph problems. Here is the complete implementation with component labeling.

python
def connected_components(graph):
    """Find all connected components in undirected graph.
    Returns: dict mapping vertex → component_id, and list of components."""
    comp_id = {}
    components = []
    current_id = 0

    for start in graph:
        if start in comp_id:
            continue
        # BFS from this unvisited vertex
        component = []
        queue = deque([start])
        comp_id[start] = current_id
        while queue:
            u = queue.popleft()
            component.append(u)
            for v in graph[u]:
                if v not in comp_id:
                    comp_id[v] = current_id
                    queue.append(v)
        components.append(component)
        current_id += 1

    return comp_id, components

# Example: friendship graph
G = {
    'Alice': ['Bob'], 'Bob': ['Alice', 'Carol'],
    'Carol': ['Bob'], 'Dave': ['Eve'],
    'Eve': ['Dave'], 'Frank': []
}
ids, comps = connected_components(G)
# comps = [['Alice','Bob','Carol'], ['Dave','Eve'], ['Frank']]
# 3 components: friend group, couple, loner

Multi-Source BFS: A Powerful Variant

Consider this problem: in a grid, some cells are "fire" sources. Fire spreads to adjacent cells each minute. How long until fire reaches every cell? This is multi-source BFS. Initialize the queue with ALL fire cells at distance 0, then run standard BFS. The wavefront expands from all sources simultaneously.

This is exactly "Rotting Oranges" (LC 994), "01 Matrix" (LC 542), and "Walls and Gates" (LC 286). The key insight: multi-source BFS is identical to regular BFS with a "virtual source" connected to all real sources. Instead of creating this virtual node explicitly, just enqueue all real sources at the start.

Application 4: BFS on Trees (Level-Order Traversal)

A tree is a special graph: connected, acyclic, V-1 edges. BFS on a tree from the root gives level-order traversal — visit all nodes at depth 0 (root), then depth 1, then depth 2. This is the basis of many tree problems: maximum depth, level averages, zigzag traversal, right-side view.

python
def level_order(root):
    """BFS level-order traversal of a binary tree."""
    if not root:
        return []
    result = []
    queue = deque([root])
    while queue:
        level = []
        for _ in range(len(queue)):  # process one level at a time
            node = queue.popleft()
            level.append(node.val)
            if node.left:  queue.append(node.left)
            if node.right: queue.append(node.right)
        result.append(level)
    return result
# The "process one level at a time" pattern (recording queue length
# before processing) is used in MANY BFS problems.

Application 4: Shortest Path Recovery

BFS computes distances, but often you need the actual path. The parent pointers π[v] give you this. To reconstruct the shortest path from s to v, follow parent pointers backwards from v to s, then reverse.

python
def shortest_path(parent, source, target):
    """Reconstruct path from BFS parent pointers."""
    if parent[target] is None and target != source:
        return None  # not reachable
    path = []
    v = target
    while v is not None:
        path.append(v)
        v = parent[v]
    return path[::-1]  # reverse to get s-to-t order

Application 5: Shortest Path in a Chess Board (Knight Moves)

What is the minimum number of knight moves to reach from position (r1, c1) to (r2, c2) on an 8x8 chess board? This is BFS on an implicit graph. Each board position is a vertex. Each legal knight move creates an edge. The graph has at most 64 vertices and 64 × 8 = 512 edges.

python
def min_knight_moves(r1, c1, r2, c2, n=8):
    """Min knight moves on nxn board from (r1,c1) to (r2,c2)."""
    moves = [(-2,-1),(-2,1),(-1,-2),(-1,2),
             (1,-2),(1,2),(2,-1),(2,1)]
    visited = set()
    visited.add((r1, c1))
    queue = deque([(r1, c1, 0)])

    while queue:
        r, c, d = queue.popleft()
        if r == r2 and c == c2:
            return d
        for dr, dc in moves:
            nr, nc = r + dr, c + dc
            if 0 <= nr < n and 0 <= nc < n and (nr, nc) not in visited:
                visited.add((nr, nc))
                queue.append((nr, nc, d + 1))
    return -1

# min_knight_moves(0, 0, 7, 7) → 6 moves
# min_knight_moves(0, 0, 1, 1) → 4 moves (not 2 — knight can't go diagonal)

Application 7: Flood Fill (LC 733)

Given a 2D image (grid of pixel colors) and a starting pixel, change the color of all connected same-color pixels. This is DFS/BFS connected component traversal on a grid, changing colors as you go.

python
def floodFill(image, sr, sc, newColor):
    """LC 733: Flood fill from (sr, sc) with newColor."""
    rows, cols = len(image), len(image[0])
    origColor = image[sr][sc]
    if origColor == newColor:
        return image  # no-op avoids infinite loop

    def dfs(r, c):
        if r < 0 or r >= rows or c < 0 or c >= cols:
            return
        if image[r][c] != origColor:
            return
        image[r][c] = newColor
        dfs(r+1, c); dfs(r-1, c)
        dfs(r, c+1); dfs(r, c-1)

    dfs(sr, sc)
    return image
# The origColor == newColor check is CRITICAL.
# Without it, DFS revisits cells endlessly
# (newColor == origColor means cells keep matching).

Complexity Analysis Deep Dive

BFS visits each vertex at most once (it is enqueued when discovered, dequeued when processed). Each edge is examined at most once (when its source vertex is dequeued, we scan its adjacency list). With adjacency lists:

The V term comes from initializing every vertex (color, distance, parent). The E term comes from scanning all adjacency lists. Together: O(V) + O(E) = O(V + E).

Space: O(V) for the color/distance/parent arrays, plus O(V) for the queue (in the worst case, all vertices are in the queue simultaneously — imagine a star graph with one center node connected to V-1 leaves). Total space: O(V).

Chapter 3: Depth-First Search

BFS spreads out like ripples. Depth-First Search (DFS) does the opposite: it dives as deep as possible down one path before backtracking. Think of exploring a maze: you follow one corridor all the way to a dead end, then backtrack to the last junction and try the next corridor. You never stop mid-corridor to explore a different one.

Timestamps: Discovery and Finish

DFS assigns two timestamps to every vertex. These timestamps are the secret weapon that makes DFS so powerful for structural analysis.

d[v] (discovery time): the moment DFS first encounters v and colors it gray. The vertex enters the "call stack."

f[v] (finish time): the moment DFS finishes processing all of v's descendants and colors it black. The vertex leaves the call stack.

A global clock ticks upward from 1. Each discovery and each finish increments the clock by 1. For a graph with V vertices, timestamps range from 1 to 2V (every vertex gets exactly one discovery and one finish). The timestamps tell you the structural history of the DFS exploration — when each vertex was entered and when it was fully processed.

Why do we need TWO timestamps? Discovery time alone tells you when DFS first reached a vertex, but not when it finished exploring that vertex's subtree. The finish time captures the moment when all descendants have been fully explored. The interval [d[v], f[v]] represents the time during which v was "active" — on the recursion stack. Two vertices' intervals either nest (ancestor-descendant) or are disjoint (no relationship). This nesting property is the Parenthesis Theorem.

The Algorithm

Runtime: Θ(V + E). Each vertex is visited exactly once (transitions white → gray → black irreversibly). Each edge is examined exactly once (when DFS-VISIT processes its source vertex). The outer loop in DFS(G) costs O(V) for checking all vertices. Each call to DFS-VISIT on vertex u costs O(1 + |Adj[u]|). Summing over all vertices: ∑ (1 + |Adj[u]|) = V + E. Total: Θ(V + E).

Space: O(V) for the recursion stack (at most V nested calls in a path graph), plus O(V) for the color, timestamp, and parent arrays. The recursion stack depth equals the length of the longest path in the DFS tree. For balanced graphs this is O(log V); for path graphs this is O(V).

The Parenthesis Theorem

The timestamps obey a beautiful nesting property. For any two vertices u and v, exactly one of three cases holds:

Case 1: [d[u], f[u]] and [d[v], f[v]] are entirely disjoint. Neither is a descendant of the other in the DFS tree.

Case 2: [d[u], f[u]] is entirely contained within [d[v], f[v]]. Then u is a descendant of v in the DFS tree.

Case 3: [d[v], f[v]] is entirely contained within [d[u], f[u]]. Then v is a descendant of u in the DFS tree.

In other words, the intervals either nest or are disjoint — they never partially overlap. This is why it is called the "parenthesis theorem": if you write an open-paren at discovery and a close-paren at finish, the result is always a valid parenthesization.

Worked Example: Timestamps By Hand

Consider a directed graph with vertices {A, B, C, D, E, F} and edges A→B, A→D, B→C, C→E, D→B, E→F, F→C. Let us trace DFS starting from A (alphabetical order for neighbor processing).

Final timestamps: A(1/12), B(2/9), C(3/8), D(10/11), E(4/7), F(5/6). Parenthesization: (A (B (C (E (F) ) ) ) (D) ). Notice: B's interval [2,9] contains C's [3,8], which contains E's [4,7], which contains F's [5,6]. All properly nested. D's interval [10,11] is disjoint from B's [2,9] — they are siblings.

Edge Classification

When DFS examines an edge (u, v), the color of v tells us what kind of edge it is:

The White-Path Theorem

Vertex v is a descendant of u in the DFS forest if and only if at time d[u] (when u is discovered), there exists a path from u to v consisting entirely of white vertices. This is CLRS Theorem 22.9.

Why is this useful? It tells you that the structure of the DFS tree depends on the order in which DFS processes vertices. Different processing orders produce different DFS trees (different tree/back/forward/cross edge classifications) — but the parenthesis theorem and white-path theorem hold for ALL of them.

Undirected Graph Edge Classification

In undirected graphs, the edge classification is simpler. When DFS examines edge {u, v}:

Tree edge: v is white. We discover v through u.

Back edge: v is gray (an ancestor of u). This is the ONLY other possibility in undirected graphs.

There are no forward or cross edges in undirected DFS. Why? If v is black and v is not u's parent, then v must have processed u as a neighbor when v was gray — so the edge was already classified as a tree or back edge from v's perspective. Every edge in an undirected graph is either a tree edge or a back edge.

Recursive vs Iterative DFS

The recursive DFS shown above is elegant but has a fatal flaw: on large graphs (V > 10,000), it can overflow Python's default recursion limit (1000). The iterative version uses an explicit stack and handles arbitrarily large graphs.

python
def dfs_iterative_timestamps(graph):
    """Iterative DFS with timestamps (handles large graphs)."""
    d, f = {}, {}
    color = {v: 'white' for v in graph}
    time = [0]
    edge_types = []

    for start in graph:
        if color[start] != 'white':
            continue
        # Stack entries: (vertex, neighbor_iterator)
        stack = [(start, iter(graph[start]))]
        time[0] += 1
        d[start] = time[0]
        color[start] = 'gray'

        while stack:
            u, neighbors = stack[-1]
            try:
                v = next(neighbors)
                if color[v] == 'white':
                    edge_types.append((u, v, 'tree'))
                    time[0] += 1
                    d[v] = time[0]
                    color[v] = 'gray'
                    stack.append((v, iter(graph[v])))
                elif color[v] == 'gray':
                    edge_types.append((u, v, 'back'))
                else:
                    etype = 'forward' if d[u] < d[v] else 'cross'
                    edge_types.append((u, v, etype))
            except StopIteration:
                color[u] = 'black'
                time[0] += 1
                f[u] = time[0]
                stack.pop()

    return d, f, edge_types

DFS Step-Through

python
def dfs(graph):
    """Full DFS with timestamps and edge classification."""
    color  = {v: 'white' for v in graph}
    d      = {}  # discovery times
    f      = {}  # finish times
    parent = {v: None for v in graph}
    edges  = []  # (u, v, type) tuples
    time   = [0]  # mutable counter

    def visit(u):
        time[0] += 1
        d[u] = time[0]
        color[u] = 'gray'
        for v in graph[u]:
            if color[v] == 'white':
                edges.append((u, v, 'tree'))
                parent[v] = u
                visit(v)
            elif color[v] == 'gray':
                edges.append((u, v, 'back'))
            elif d[u] < d[v]:
                edges.append((u, v, 'forward'))
            else:
                edges.append((u, v, 'cross'))
        color[u] = 'black'
        time[0] += 1
        f[u] = time[0]

    for u in graph:
        if color[u] == 'white':
            visit(u)

    return d, f, parent, edges

Chapter 4: DFS Applications

DFS timestamps and edge classification unlock two critical algorithms: cycle detection and topological sorting. Both rely on the same insight — back edges reveal cycles, and the absence of back edges means the graph can be linearly ordered.

Cycle Detection

A directed graph has a cycle if and only if DFS discovers a back edge. This follows directly from the edge classification: a back edge (u, v) means v is an ancestor of u on the current DFS path. The path from v down to u through the DFS tree, plus the back edge from u back to v, forms a cycle.

For undirected graphs, the rule is simpler: any edge to an already-visited vertex (that is not the parent) indicates a cycle. We do not need timestamps — just parent tracking.

python
def has_cycle_directed(graph):
    """Returns True if directed graph has a cycle."""
    color = {v: 'white' for v in graph}

    def visit(u):
        color[u] = 'gray'
        for v in graph[u]:
            if color[v] == 'gray':
                return True   # back edge = cycle!
            if color[v] == 'white' and visit(v):
                return True
        color[u] = 'black'
        return False

    for u in graph:
        if color[u] == 'white' and visit(u):
            return True
    return False

Theorem: Directed Graph Has Cycle ⇔ DFS Finds Back Edge

This is CLRS Lemma 22.11. Let us prove both directions.

(⇒) If DFS finds back edge (u, v), then G has a cycle. A back edge means v is gray when u examines it — v is an ancestor of u on the current DFS path. The path from v down the DFS tree to u, plus the back edge from u to v, forms a cycle. Done.

(⇐) If G has a cycle, then DFS finds a back edge. Let C = v₁ → v₂ → ... → v_k → v₁ be a cycle. Let v_i be the first vertex in C discovered by DFS. At time d[v_i], by the White-Path Theorem, there is a white path from v_i to v_i-1 (going around the cycle). So v_i-1 becomes a descendant of v_i. When DFS processes v_i-1, it examines the edge v_i-1 → v_i. At this point, v_i is still gray (it started before v_i-1 and finishes after). So this edge is classified as a back edge. Done.

Interactive Cycle Detector

Cycle Detection in Undirected Graphs

For undirected graphs, cycle detection is slightly different. Every edge appears twice in the adjacency list (once for each endpoint). When DFS from u visits neighbor v, and v is already visited but v is NOT u's parent, we have found a cycle. We need the parent check because in an undirected graph, the edge {u, v} naturally appears when we process u from v — that is not a cycle, just the same edge traversed backwards.

python
def has_cycle_undirected(graph):
    """Cycle detection in undirected graph."""
    visited = set()

    def dfs(u, parent):
        visited.add(u)
        for v in graph[u]:
            if v not in visited:
                if dfs(v, u):
                    return True
            elif v != parent:
                return True  # visited and not parent = cycle!
        return False

    for u in graph:
        if u not in visited:
            if dfs(u, None):
                return True
    return False

Extracting the Actual Cycle

Finding that a cycle exists is step one. Often you need the cycle itself. When DFS detects back edge (u, v), the cycle is: v → ... → u → v. Walk up the DFS parent chain from u to v to extract it.

python
def find_cycle_directed(graph):
    """Returns the cycle as a list, or None."""
    color  = {v: 'white' for v in graph}
    parent = {v: None for v in graph}

    def visit(u):
        color[u] = 'gray'
        for v in graph[u]:
            if color[v] == 'gray':
                # Back edge (u, v). Extract cycle.
                cycle = [v, u]
                w = u
                while parent[w] != v:
                    w = parent[w]
                    cycle.append(w)
                cycle.append(v)
                return cycle[::-1]
            if color[v] == 'white':
                parent[v] = u
                result = visit(v)
                if result:
                    return result
        color[u] = 'black'
        return None

    for u in graph:
        if color[u] == 'white':
            result = visit(u)
            if result:
                return result
    return None

From Cycles to Ordering

If DFS finds NO back edges, the graph is a Directed Acyclic Graph (DAG). DAGs are special because their vertices can be topologically sorted — arranged in a linear order such that for every edge (u, v), u appears before v. Think: you can take all courses in an order that respects every prerequisite.

CLRS Theorem 22.11: DAG ⇔ No Back Edges (Formal)

A directed graph G is a DAG if and only if a DFS of G yields no back edges. This is the formal version of what we proved for cycles. The forward direction: if G is a DAG, then no cycle exists, so no back edge exists (since every back edge creates a cycle). The reverse: if DFS produces no back edges, then every edge goes from a vertex to a descendant (tree/forward) or a previously finished vertex (cross). In all these cases f[u] > f[v] for edge (u, v), meaning there is a topological order, meaning no cycle exists, meaning G is a DAG.

This theorem connects three equivalent statements: (1) G is a DAG, (2) DFS on G has no back edges, (3) G has a topological ordering. Any one implies the other two. This triangle of equivalences is the foundation of Chapters 4 and 5.

Chapter 5: Topological Sort

You are registering for university courses. CS201 requires CS101. CS301 requires CS201 and MATH201. MATH201 requires MATH101. In what order should you take these courses so that every prerequisite is satisfied before you take the course that needs it?

This is topological sorting: given a DAG, produce a linear ordering of vertices such that for every edge (u, v), vertex u appears before vertex v. Topological sort only works on DAGs — if there is a cycle, no valid ordering exists (you would need to take CS201 before CS101, which requires CS201).

Topological sort is one of the most frequently used graph algorithms in practice. Build systems, package managers, task schedulers, spreadsheet formula evaluation, event processing, data pipeline orchestration — all rely on topological sort. If you learn one algorithm from this chapter, make it topological sort.

Method 1: DFS-Based (Reverse Finish Order)

We derived this in the previous chapter. Run DFS on the entire graph. As each vertex finishes (turns black), prepend it to a list. The resulting list is a valid topological order.

python
def topological_sort_dfs(graph):
    """Topological sort via DFS (reverse finish order)."""
    color = {v: 'white' for v in graph}
    order = []

    def visit(u):
        color[u] = 'gray'
        for v in graph[u]:
            if color[v] == 'gray':
                raise ValueError("Graph has a cycle!")
            if color[v] == 'white':
                visit(v)
        color[u] = 'black'
        order.append(u)  # append on finish

    for u in graph:
        if color[u] == 'white':
            visit(u)

    return order[::-1]  # reverse for topological order

Method 2: Kahn's Algorithm (BFS with In-Degree)

There is a second way that does not use DFS at all. Kahn's algorithm works by repeatedly removing vertices with no incoming edges (in-degree 0). The intuition: a vertex with no prerequisites can be placed first. Remove it, decrement the in-degree of its neighbors. Some neighbors now have in-degree 0 — they can go next. Repeat until the graph is empty.

python
from collections import deque

def topological_sort_kahn(graph):
    """Topological sort via Kahn's algorithm (BFS + in-degree)."""
    in_deg = {v: 0 for v in graph}
    for u in graph:
        for v in graph[u]:
            in_deg[v] += 1

    queue = deque(v for v in graph if in_deg[v] == 0)
    order = []

    while queue:
        u = queue.popleft()
        order.append(u)
        for v in graph[u]:
            in_deg[v] -= 1
            if in_deg[v] == 0:
                queue.append(v)

    if len(order) != len(graph):
        raise ValueError("Graph has a cycle!")
    return order

Uniqueness of Topological Order

A DAG can have multiple valid topological orderings. Consider a DAG with edges A→C, B→C. Both [A, B, C] and [B, A, C] are valid. The topological order is unique if and only if there is a Hamiltonian path (a path visiting every vertex) in the DAG — equivalently, at every step of Kahn's algorithm, the queue has exactly one element.

Topological Sort on a DAG with Parallel Levels

A variant asks: what is the minimum number of time steps if tasks at the same "level" can be parallelized? This is the longest path in the DAG, which equals the number of rounds in Kahn's algorithm. Each round of Kahn's processes all current zero-in-degree vertices simultaneously.

python
def parallel_stages(graph):
    """Number of parallel stages = longest path + 1."""
    in_deg = {v: 0 for v in graph}
    for u in graph:
        for v in graph[u]:
            in_deg[v] += 1

    queue = deque(v for v in graph if in_deg[v] == 0)
    stages = 0

    while queue:
        stages += 1
        next_queue = deque()
        for _ in range(len(queue)):
            u = queue.popleft()
            for v in graph[u]:
                in_deg[v] -= 1
                if in_deg[v] == 0:
                    next_queue.append(v)
        queue = next_queue

    return stages
# CS101, MATH101 can be taken in parallel (stage 1)
# CS201, MATH201 in parallel (stage 2) ... etc.

Worked Example: Course Prerequisites

Kahn's algorithm trace:

Final order: CS101, MATH101, CS201, MATH201, CS301, CS401. All 6 courses processed, so no cycle. This is a valid graduation plan.

DFS-based trace: DFS from CS101: CS101→CS201→CS301→CS401. Finish: CS401(f=1), CS301(f=2), CS201(f=3), CS101(f=4). Then DFS from MATH101: MATH101→MATH201→CS301(already visited). Finish: MATH201(f=5), MATH101(f=6). Reverse finish order: MATH101, MATH201, CS101, CS201, CS301, CS401. Also valid!

Kahn's Algorithm: Why It Works

The correctness of Kahn's algorithm relies on a simple inductive argument. At each step, we remove a vertex with in-degree 0. This vertex has no unprocessed predecessors, so it can safely come next in the topological order. After removing it, we decrement the in-degree of its successors — which might create new zero-in-degree vertices.

Correctness proof sketch: Suppose Kahn's outputs order [v₁, v₂, ..., v_n]. Consider any edge (v_i, v_j). When v_i was dequeued, v_j's in-degree was decremented. v_j was enqueued only after all its predecessors (including v_i) were processed. So i < j. Every edge goes from earlier to later in the order. This is exactly the topological ordering property.

Cycle detection: If the graph has a cycle C, no vertex in C ever reaches in-degree 0 (each vertex in C always has at least one unprocessed predecessor in C). So Kahn's cannot dequeue any vertex in C, and |output| < |V|. The "leftover" vertices are exactly those participating in cycles.

Interview Problem: Course Schedule II (LC 210)

Given numCourses and prerequisite pairs, return a valid course order (topological order). If impossible (cycle), return empty array. This is the quintessential topological sort interview problem.

python
def findOrder(numCourses, prerequisites):
    """LC 210: Return a valid topological order or []."""
    graph = [[] for _ in range(numCourses)]
    in_deg = [0] * numCourses
    for course, prereq in prerequisites:
        graph[prereq].append(course)
        in_deg[course] += 1

    queue = deque(i for i in range(numCourses) if in_deg[i] == 0)
    order = []

    while queue:
        u = queue.popleft()
        order.append(u)
        for v in graph[u]:
            in_deg[v] -= 1
            if in_deg[v] == 0:
                queue.append(v)

    return order if len(order) == numCourses else []

# Example:
# findOrder(4, [[1,0],[2,0],[3,1],[3,2]])
# Returns [0, 1, 2, 3] or [0, 2, 1, 3] (both valid)

Interview Problem: Alien Dictionary (LC 269)

Given a sorted list of words in an alien language, determine the character ordering. This is topological sort in disguise. Compare consecutive words to extract ordering constraints: if word[i] differs from word[i+1] at position j, then word[i][j] comes before word[i+1][j] in the alien alphabet. Build a graph of these constraints and topologically sort.

python
def alienOrder(words):
    """LC 269: Topological sort on character ordering."""
    # Build graph from adjacent word comparisons
    graph = {c: set() for w in words for c in w}
    in_deg = {c: 0 for c in graph}

    for i in range(len(words) - 1):
        w1, w2 = words[i], words[i + 1]
        # Edge case: "abc" before "ab" is invalid
        if len(w1) > len(w2) and w1[:len(w2)] == w2:
            return ""
        for j in range(min(len(w1), len(w2))):
            if w1[j] != w2[j]:
                if w2[j] not in graph[w1[j]]:
                    graph[w1[j]].add(w2[j])
                    in_deg[w2[j]] += 1
                break

    # Kahn's topological sort
    queue = deque(c for c in in_deg if in_deg[c] == 0)
    result = []
    while queue:
        c = queue.popleft()
        result.append(c)
        for n in graph[c]:
            in_deg[n] -= 1
            if in_deg[n] == 0:
                queue.append(n)

    return "".join(result) if len(result) == len(graph) else ""

Interactive Topological Sort

Chapter 6: Strongly Connected Components

In a directed graph, vertex u can reach vertex v, but can v reach u? When both directions are possible — every vertex can reach every other vertex — the group forms a strongly connected component (SCC). SCCs are the "clusters of mutual reachability" in a directed graph.

Formally, an SCC is a maximal set of vertices C ⊆ V such that for every pair u, v ∈ C, both u ↝ v and v ↝ u (there are directed paths in both directions). Maximal means you cannot add any more vertices to C without breaking the mutual reachability property.

How many SCCs can a graph have? At most V (every vertex is its own SCC — no edges). At least 1 (the whole graph is one SCC — like a single big cycle). A DAG has exactly V SCCs (each vertex is its own, since no vertex can reach itself through a non-trivial cycle).

How Many SCCs Does a Graph Have?

The number of SCCs is between 1 (the entire graph is one SCC — a single strongly connected component, like a big cycle that visits every vertex) and V (every vertex is its own SCC — the graph is a DAG with no non-trivial cycles).

A graph has exactly 1 SCC if and only if it is strongly connected: for every pair of vertices u, v, there exist paths u↝v and v↝u. A graph has V SCCs if and only if it is a DAG. In between, the number of SCCs tells you "how far from being a DAG" the graph is — more SCCs means more DAG-like structure, fewer SCCs means more cyclic structure.

Kosaraju's Algorithm

Kosaraju's algorithm finds all SCCs in two DFS passes. It is conceptually simple and uses a beautiful symmetry argument.

Why does this work? The argument hinges on a key lemma (CLRS Lemma 22.14): if there is an edge from SCC C to SCC C' in the component graph, then the maximum finish time in C is greater than the maximum finish time in C'. This is because C can reach C' (via the edge), so when DFS enters C, it will discover all of C' before finishing all of C.

Now in Step 3, we process vertices in decreasing finish time. The first vertex we process belongs to the SCC with the highest finish time — call it C_max. In G^T, all edges are reversed. C_max had the highest finish time, meaning in the original graph, it had edges TO other SCCs. In G^T, those edges point FROM other SCCs INTO C_max. So DFS from C_max in G^T can only reach vertices within C_max — the reversed edges prevent it from escaping into other SCCs. The first DFS tree is exactly C_max.

After removing C_max, the next unvisited vertex with highest finish time belongs to the next SCC in the component DAG ordering. The same argument applies: DFS in G^T from this vertex discovers exactly its SCC and nothing more. This continues until all SCCs are found.

python
def kosaraju(graph):
    """Find SCCs using Kosaraju's algorithm."""
    # Step 1: DFS on G, record finish order
    visited = set()
    finish_stack = []

    def dfs1(u):
        visited.add(u)
        for v in graph[u]:
            if v not in visited:
                dfs1(v)
        finish_stack.append(u)  # push on finish

    for u in graph:
        if u not in visited:
            dfs1(u)

    # Step 2: Build transpose graph
    g_t = {v: [] for v in graph}
    for u in graph:
        for v in graph[u]:
            g_t[v].append(u)

    # Step 3: DFS on G^T in reverse finish order
    visited2 = set()
    sccs = []

    def dfs2(u, component):
        visited2.add(u)
        component.append(u)
        for v in g_t[u]:
            if v not in visited2:
                dfs2(v, component)

    while finish_stack:
        u = finish_stack.pop()  # highest finish time first
        if u not in visited2:
            comp = []
            dfs2(u, comp)
            sccs.append(comp)

    return sccs

Tarjan's Algorithm

Tarjan's algorithm finds SCCs in a single DFS pass using a clever trick: low-link values. The low-link of a vertex u is the smallest discovery time reachable from u by following tree edges downward and at most one back edge upward. If low[u] == d[u], then u is the root of an SCC — no vertex in its subtree can "escape" to an ancestor above u.

python
def tarjan(graph):
    """Find SCCs using Tarjan's algorithm (single DFS)."""
    index_counter = [0]
    stack = []
    on_stack = set()
    d = {}
    low = {}
    sccs = []

    def strongconnect(u):
        d[u] = low[u] = index_counter[0]
        index_counter[0] += 1
        stack.append(u)
        on_stack.add(u)

        for v in graph[u]:
            if v not in d:  # not visited
                strongconnect(v)
                low[u] = min(low[u], low[v])
            elif v in on_stack:
                low[u] = min(low[u], d[v])

        if low[u] == d[u]:  # root of SCC
            component = []
            while True:
                w = stack.pop()
                on_stack.discard(w)
                component.append(w)
                if w == u:
                    break
            sccs.append(component)

    for u in graph:
        if u not in d:
            strongconnect(u)

    return sccs

Worked Example: SCCs By Hand

Consider this directed graph: A→B, B→C, C→A (cycle 1), C→D, D→E, E→F, F→D (cycle 2), E→G (G is a sink).

Kosaraju's Step 1 — DFS on G: Start from A. Visit A(d=1)→B(d=2)→C(d=3)→D(d=4)→E(d=5)→F(d=6). F→D but D is gray (back edge). Finish F(f=7), finish E... wait, E also has E→G. Visit G(d=8), finish G(f=9). Finish E(f=10), D(f=11). C→A but A is gray (back edge). Finish C(f=12), B(f=13), A(f=14).

Finish stack (top first): A(14), B(13), C(12), D(11), E(10), G(9), F(7).

Kosaraju's Step 2 — Transpose G^T: Reverse every edge: B→A, C→B, A→C, D→C, E→D, F→E, D→F, G→E.

Kosaraju's Step 3 — DFS on G^T in finish order:

Result: 3 SCCs: {A,B,C}, {D,E,F}, {G}. The component DAG: {A,B,C} → {D,E,F} → {G}.

The Component DAG

Once you have the SCCs, you can build the component graph (also called the condensation). Replace each SCC with a single vertex. Add an edge between two super-vertices if any vertex in one SCC has an edge to any vertex in the other SCC. The component graph is always a DAG (Lemma 22.13 in CLRS).

python
def build_component_dag(graph, sccs):
    """Build DAG of SCCs (condensation)."""
    # Map each vertex to its SCC index
    scc_id = {}
    for i, scc in enumerate(sccs):
        for v in scc:
            scc_id[v] = i

    # Build condensation DAG
    dag = {i: set() for i in range(len(sccs))}
    for u in graph:
        for v in graph[u]:
            if scc_id[u] != scc_id[v]:
                dag[scc_id[u]].add(scc_id[v])

    return {k: list(v) for k, v in dag.items()}

Tarjan's Worked Example

Same graph: A→B, B→C, C→A, C→D, D→E, E→F, F→D, E→G. Let us trace Tarjan's algorithm.

Result: SCCs are {G}, {D,E,F}, {A,B,C} — same answer as Kosaraju's, found in a single DFS pass. The key insight: when we return from recursion and find low[u] == d[u], everything on the stack above u (including u) forms an SCC. They are all mutually reachable because the low-link values propagated back edges upward, proving circular reachability.

When to Use SCCs in Practice

SCC decomposition is a preprocessing step for many problems on directed graphs:

• 2-SAT: Build an implication graph, find SCCs. A variable and its negation in the same SCC = unsatisfiable.
• Minimum vertices to reach all vertices: Find SCCs with zero in-degree in the component DAG.
• Redundant connections: Edges within the same SCC are redundant for reachability (the SCC is already mutually reachable).
• Course equivalence: If course A requires B and B requires A, they form an SCC — you must take them together.
• Minimum edges to make graph strongly connected: Find the component DAG. Count sources (in-degree 0) and sinks (out-degree 0) in the component DAG. Answer = max(sources, sinks) if graph has >1 SCC, else 0.

SCC Interview Problem: Critical Connections (LC 1192)

Find all bridges (critical connections) in a graph — edges whose removal disconnects the graph. This uses the same DFS + low-link technique as Tarjan's SCC, adapted for undirected graphs. An edge (u, v) is a bridge if and only if low[v] > d[u] — meaning v's subtree has no back edge that reaches u or above.

python
def criticalConnections(n, connections):
    """LC 1192: Find all bridges in undirected graph."""
    graph = [[] for _ in range(n)]
    for u, v in connections:
        graph[u].append(v)
        graph[v].append(u)

    d = [0] * n
    low = [0] * n
    visited = [False] * n
    bridges = []
    timer = [0]

    def dfs(u, parent):
        visited[u] = True
        timer[0] += 1
        d[u] = low[u] = timer[0]
        for v in graph[u]:
            if v == parent:
                continue
            if not visited[v]:
                dfs(v, u)
                low[u] = min(low[u], low[v])
                if low[v] > d[u]:  # v can't reach u without (u,v)
                    bridges.append([u, v])
            else:
                low[u] = min(low[u], d[v])

    dfs(0, -1)
    return bridges

The SCC Showcase Simulation

This is the payoff. The simulation below shows a directed graph with multiple SCCs. Choose Kosaraju's or Tarjan's algorithm, then step through (or auto-play). Watch SCCs light up as they are discovered. The component DAG forms at the bottom.

Chapter 7: Graph Problems in Practice

Everything in Chapters 1-6 was theory. Now let us see where these algorithms appear in real systems. Every example below is a production system you use daily.

Social Networks: Connected Components

Facebook has ~3 billion users. "People you may know" suggestions start with BFS from your profile. Finding all friend clusters (connected components) uses repeated BFS/DFS. The vast majority of Facebook users are in one giant connected component — it is called the "giant component" phenomenon in network science.

Build Systems: Topological Sort

When you type make or gradle build, the build system constructs a dependency graph: source files, object files, libraries. It topologically sorts this graph to determine compilation order. If a cycle exists (A depends on B, B depends on A), the build system reports a circular dependency error — that is Kahn's algorithm detecting |order| < |V|.

Web Crawling: BFS

Google's web crawler starts from seed URLs and explores the web using BFS. Each URL is a vertex. Each hyperlink is a directed edge. BFS ensures that pages close to the seeds (high-authority pages) are crawled first. The "depth" of BFS corresponds to how many clicks away a page is from the seed.

Deadlock Detection: Cycle Detection

In operating systems, processes wait for resources held by other processes. This creates a wait-for graph: vertices are processes, edges represent "process A waits for process B." A cycle in this graph is a deadlock — a group of processes waiting for each other forever. The OS kernel runs periodic DFS cycle detection on this graph.

Package Managers: SCCs + Topological Sort

When npm install or pip install resolves dependencies, it builds a dependency graph. Circular dependencies form SCCs. The package manager collapses each SCC into a group that must be installed together, then topologically sorts the resulting DAG to determine installation order.

Compilers: SCCs for Optimization

In compiler optimization, the call graph (which functions call which) is analyzed using SCCs. Each SCC is a group of mutually recursive functions. The compiler can inline or optimize within an SCC as a unit, then process SCCs in reverse topological order of the component DAG.

Google PageRank: BFS + Graph Structure

Google's original PageRank algorithm models the web as a directed graph (pages are vertices, hyperlinks are edges). The algorithm performs a random walk: at each step, follow a random outgoing link (with probability 0.85) or jump to a random page (probability 0.15). The stationary distribution of this random walk gives the "importance" of each page. Finding this distribution requires iterating over the graph structure — and understanding SCCs is crucial because pages in the same SCC reinforce each other's importance.

Neural Network Computation Graphs

Deep learning frameworks (PyTorch, TensorFlow) represent computations as DAGs. Each operation (matmul, ReLU, softmax) is a vertex. Data dependencies are edges. Forward pass = topological sort of this DAG. Backward pass = reverse topological sort. Understanding Chapter 22 literally explains how autograd works.

Internet Routing: BFS on the Network

The Internet is a graph of routers connected by physical links. Routing protocols like OSPF (Open Shortest Path First) use Dijkstra's algorithm — which is essentially BFS with a priority queue. Each router builds a "link-state database" (the graph), runs Dijkstra, and builds a shortest-path tree. Every packet you send follows BFS-optimal paths through the network.

Version Control: DAGs Everywhere

Git's commit history is a DAG. Each commit points to its parent(s). Merge commits have two parents. Branches are pointers to commits. When you run git log --graph, you are looking at a DAG. Topological sort of this DAG gives you a valid linear history. Finding the common ancestor of two branches (for merge resolution) is a graph reachability problem — specifically, lowest common ancestor in a DAG.

Garbage Collection: DFS Marking

The mark-and-sweep garbage collector in languages like Java and Python uses DFS to find reachable objects. Starting from "root" references (global variables, stack variables), DFS traverses the object reference graph. Every reachable object is "marked." After DFS completes, unmarked objects are unreachable (garbage) and can be freed. This is literally DFS on the heap — the most performance-critical graph algorithm in most programs.

Database Query Optimization

When you write a SQL query joining 5 tables, the query optimizer builds a join graph (tables = vertices, join conditions = edges). It finds the optimal join order using graph analysis. Cycle detection identifies redundant join conditions. Topological sort (for DAG-shaped joins) determines execution order. Connected components identify independent subqueries that can be parallelized.

Real-World Scale: Where These Algorithms Run

Full Example: Analyzing a Codebase

Imagine you are analyzing a codebase with module dependencies. Here is the full workflow using the algorithms from this chapter:

Build System Simulator

Chapter 8: BFS vs DFS

Both BFS and DFS run in O(V + E). Both visit every vertex and every edge exactly once. But they explore the graph in fundamentally different orders, which makes each one the right tool for different problems. This chapter is your decision guide.

The Core Difference

BFS uses a queue (FIFO). It explores all neighbors at distance k before any at distance k+1. It produces a shortest-path tree from the source. Think: expanding wavefront, concentric circles, "how far away is everything?"

DFS uses a stack (LIFO, or recursion). It plunges deep into one path before backtracking. It produces timestamps (discovery/finish) and a DFS forest. Think: maze exploration, "what is the structure of this graph?"

When to Use Which

Use BFS when:

• You need shortest paths in an unweighted graph
• You need level-order traversal (e.g., tree levels, BFS-level grouping)
• You need to test bipartiteness
• The graph is wide and shallow (BFS queue stays small)
• You are doing multi-source BFS (e.g., "nearest exit" from every cell in a maze)

Use DFS when:

• You need cycle detection in directed graphs
• You need topological sort
• You need strongly connected components
• You need articulation points or bridges
• You are solving backtracking problems (permutations, combinations, Sudoku)
• The graph is narrow and deep (DFS stack stays small)

Space Comparison on Extreme Graphs

Both BFS and DFS use O(V) space in the worst case, but on specific graph shapes, one can be dramatically better than the other.

Bidirectional BFS

When searching for a path between two specific vertices s and t, bidirectional BFS runs two BFS simultaneously — one from s, one from t. When the two frontiers meet, we have found the shortest path. This reduces the search space dramatically.

In a graph where each vertex has degree b and the shortest path has length d, regular BFS explores O(b^d) vertices. Bidirectional BFS explores O(2 × b^d/2) = O(b^d/2) — exponentially less. For the "six degrees of separation" problem on a social network (b=150, d=6), regular BFS might explore 150⁶ ≈ 10¹³ nodes, while bidirectional BFS explores 2 × 150³ ≈ 7 × 10⁶.

python
def bidirectional_bfs(graph, s, t):
    """Returns shortest path length from s to t, or -1."""
    if s == t:
        return 0
    front_s = {s}    # frontier expanding from s
    front_t = {t}    # frontier expanding from t
    visited_s = {s}  # all visited from s side
    visited_t = {t}  # all visited from t side
    dist = 0

    while front_s and front_t:
        # Always expand the smaller frontier (optimization)
        if len(front_s) > len(front_t):
            front_s, front_t = front_t, front_s
            visited_s, visited_t = visited_t, visited_s
        dist += 1
        next_front = set()
        for u in front_s:
            for v in graph[u]:
                if v in visited_t:
                    return dist  # frontiers met!
                if v not in visited_s:
                    visited_s.add(v)
                    next_front.add(v)
        front_s = next_front
    return -1

Iterative Deepening DFS (IDDFS)

What if you want BFS's shortest-path guarantee with DFS's memory efficiency? Iterative Deepening DFS runs DFS with depth limit 0, then 1, then 2, etc. It finds the shallowest goal like BFS but uses O(d) memory like DFS (where d is the solution depth). The "wasted" re-exploration at each depth is only a constant factor: the last iteration dominates.

0-1 BFS: When Edges Have Weights 0 or 1

A special case worth knowing: if every edge weight is either 0 or 1, you can find shortest paths in O(V + E) using a deque instead of a priority queue. When processing edge (u, v): if weight = 0, push v to the front of the deque. If weight = 1, push v to the back. This maintains the invariant that the deque is sorted by distance.

python
def bfs_01(graph, source):
    """Shortest paths when edge weights are 0 or 1.
    graph[u] = [(v, weight), ...] where weight ∈ {0, 1}."""
    dist = {v: float('inf') for v in graph}
    dist[source] = 0
    dq = deque([source])

    while dq:
        u = dq.popleft()
        for v, w in graph[u]:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                if w == 0:
                    dq.appendleft(v)  # front — process soon
                else:
                    dq.append(v)       # back — process later

    return dist
# Useful for: grids where some moves are free (e.g., walking
# on ice = weight 0, walking on ground = weight 1)

The Decision Tree

Use this flowchart when facing any graph problem in an interview. Start at the top and follow the branches.

Performance on Different Graph Shapes

The theoretical runtime of both BFS and DFS is O(V + E), but constant factors and memory access patterns differ by graph shape.

BFS vs DFS Side-by-Side

Summary: The BFS vs DFS Decision Matrix

When in doubt, use this rapid decision matrix:

Chapter 9: Interview Arsenal

Graph problems are among the most common in coding interviews. This chapter gives you the patterns, the LeetCode classics, and the debugging strategies.

The Graph Problem Identification Checklist

When you see a coding problem, ask these questions to determine if it is a graph problem and which algorithm to use:

Classic LeetCode Patterns

Pattern 1: Number of Islands (LC 200) — Connected Components

Given a 2D grid of '1' (land) and '0' (water), count islands. Each island is a connected component of '1' cells. For each unvisited '1', BFS/DFS to mark all connected land cells as visited. Count the number of BFS/DFS calls.

python
def numIslands(grid):
    rows, cols = len(grid), len(grid[0])
    count = 0

    def dfs(r, c):
        if r < 0 or r >= rows or c < 0 or c >= cols:
            return
        if grid[r][c] != '1':
            return
        grid[r][c] = '0'  # mark visited
        dfs(r+1, c); dfs(r-1, c)
        dfs(r, c+1); dfs(r, c-1)

    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == '1':
                count += 1
                dfs(r, c)
    return count

Pattern 2: Course Schedule (LC 207) — Cycle Detection / Topological Sort

Given n courses and prerequisite pairs, determine if you can finish all courses. This is: "does the prerequisite graph have a cycle?" Use DFS cycle detection or Kahn's algorithm.

python
def canFinish(numCourses, prerequisites):
    graph = [[] for _ in range(numCourses)]
    in_deg = [0] * numCourses
    for a, b in prerequisites:
        graph[b].append(a)  # b is prereq of a
        in_deg[a] += 1

    # Kahn's algorithm
    queue = deque(i for i in range(numCourses) if in_deg[i] == 0)
    count = 0
    while queue:
        u = queue.popleft()
        count += 1
        for v in graph[u]:
            in_deg[v] -= 1
            if in_deg[v] == 0:
                queue.append(v)
    return count == numCourses  # all courses processable = no cycle

Pattern 3: Word Ladder (LC 127) — BFS Shortest Path

Transform "hit" to "cog" by changing one letter at a time, each intermediate word must be in the dictionary. This is BFS on an implicit graph: each word is a vertex, two words are connected if they differ by one letter. BFS finds the shortest transformation sequence.

python
def ladderLength(beginWord, endWord, wordList):
    wordSet = set(wordList)
    if endWord not in wordSet:
        return 0
    queue = deque([(beginWord, 1)])
    visited = {beginWord}
    while queue:
        word, steps = queue.popleft()
        for i in range(len(word)):
            for c in 'abcdefghijklmnopqrstuvwxyz':
                newWord = word[:i] + c + word[i+1:]
                if newWord == endWord:
                    return steps + 1
                if newWord in wordSet and newWord not in visited:
                    visited.add(newWord)
                    queue.append((newWord, steps + 1))
    return 0
# Key insight: the graph is IMPLICIT — we never build adjacency
# lists. For each word, we try all 26*len single-char replacements.

Pattern 4: Clone Graph (LC 133) — BFS/DFS with Hash Map

Deep-copy a graph. BFS/DFS through the original, maintaining a hash map from original node to cloned node. When you visit a neighbor, check if it is already cloned; if not, clone it and enqueue/recurse.

Pattern 5: Rotting Oranges (LC 994) — Multi-Source BFS

All rotten oranges spread simultaneously. This is multi-source BFS: enqueue all rotten oranges at time 0, then BFS. Each level of BFS represents one minute. The answer is the maximum distance (or -1 if any fresh orange is unreachable).

Pattern 6: Graph Valid Tree (LC 261) — Undirected Cycle Detection

A graph is a valid tree if and only if it is connected AND has no cycles. Check: (1) E == V-1 (necessary for tree), (2) BFS/DFS from any vertex visits all V vertices (connected), (3) No cycle detected. Any two of these conditions imply the third.

The Implicit Graph Pattern

Many problems have graphs that are not given as adjacency lists. Instead, the graph is implicit in the problem structure. Recognizing the implicit graph is the hardest part.

python
# Universal grid BFS template
def grid_bfs(grid, start_r, start_c):
    rows, cols = len(grid), len(grid[0])
    visited = [[False] * cols for _ in range(rows)]
    visited[start_r][start_c] = True
    queue = deque([(start_r, start_c, 0)])  # (row, col, dist)

    while queue:
        r, c, dist = queue.popleft()
        for dr, dc in [(-1,0),(1,0),(0,-1),(0,1)]:
            nr, nc = r + dr, c + dc
            if 0 <= nr < rows and 0 <= nc < cols:
                if not visited[nr][nc] and grid[nr][nc] != '#':
                    visited[nr][nc] = True
                    queue.append((nr, nc, dist + 1))
    # Adapt return value to the specific problem

Debug Scenarios

Interview debugging questions test whether you can systematically diagnose graph algorithm failures. Here are the most common.

Debug 1: "My BFS returns wrong shortest path distances"

Likely cause: Marking vertices as visited when dequeued instead of when enqueued. If you mark on dequeue, a vertex can be enqueued multiple times (once from each neighbor that discovers it). The first enqueue has the correct distance, but later enqueues overwrite it with longer distances. Fix: Always mark visited (set color to gray) at enqueue time, not at dequeue time.

Debug 2: "My DFS cycle detection has false positives on directed graphs"

Likely cause: Using a simple "visited" set instead of the three-color scheme. With just visited/unvisited, you cannot distinguish back edges (cycle) from cross/forward edges (no cycle). When you visit a neighbor that is already visited, it might be in a completely different DFS branch. Fix: Use three colors (white/gray/black). Only gray neighbors indicate cycles.

Debug 3: "My topological sort sometimes produces invalid orders"

Likely cause: Forgetting to reverse the DFS finish order. DFS appends vertices on finish, giving reverse topological order. If you return this list directly without reversing, dependencies point the wrong way. Fix: Return order[::-1] or prepend to a deque.

Debug 4: "Kosaraju's gives wrong SCCs"

Likely cause: Running the second DFS on G instead of G^T, or processing vertices in the wrong order (increasing finish time instead of decreasing). Fix: Step 2 must use the transpose graph. Step 3 must process vertices in decreasing finish time (pop from the finish stack).

Debug 5: "My graph algorithm TLEs on large inputs"

Likely causes: (1) Using adjacency matrix O(V²) instead of adjacency list O(V+E) for a sparse graph. (2) Not marking visited early enough (BFS enqueues same vertex multiple times). (3) Rebuilding the graph inside a loop. (4) Using slow set operations in Python (try deque instead of list for BFS queue). Fix: Profile to find the bottleneck. Usually it is representation or visited-set timing.

Common Interview Mistakes

Union-Find: An Alternative for Connected Components

For the specific problem of connected components in undirected graphs, there is a competing data structure: Union-Find (Disjoint Set Union, DSU). Instead of BFS/DFS, you process edges one at a time, merging components. With path compression and union by rank, each operation takes nearly O(1) amortized (technically O(α(V)) where α is the inverse Ackermann function — practically a constant).

python
class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n
        self.count = n  # number of components

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

    def union(self, x, y):
        rx, ry = self.find(x), self.find(y)
        if rx == ry:
            return False  # already connected
        if self.rank[rx] < self.rank[ry]:
            rx, ry = ry, rx
        self.parent[ry] = rx  # union by rank
        if self.rank[rx] == self.rank[ry]:
            self.rank[rx] += 1
        self.count -= 1
        return True

# Usage: process edges to find connected components
uf = UnionFind(5)
uf.union(0, 1); uf.union(2, 3); uf.union(1, 3)
# Components: {0,1,2,3} and {4}. uf.count = 2

Iterative DFS (Avoid Stack Overflow)

python
def dfs_iterative(graph, source):
    """Iterative DFS using explicit stack."""
    visited = set()
    stack = [source]
    order = []
    while stack:
        u = stack.pop()
        if u in visited:
            continue
        visited.add(u)
        order.append(u)
        for v in reversed(graph[u]):  # reversed to match recursive order
            if v not in visited:
                stack.append(v)
    return order

Interview Template: How to Approach Any Graph Problem

Here is the step-by-step template for graph problems in interviews. Follow this and you will never freeze.

The "Graph in Disguise" Pattern

The hardest graph problems do not look like graph problems. The key insight is recognizing the hidden graph structure. Here are the disguises:

Coding Drills

Practice these patterns until they are muscle memory. Each one is a 5-minute coding drill that reinforces a key graph concept.

Drill 1: Build adjacency list from edge list

python
def build_adj_list(n, edges, directed=True):
    """Build adjacency list from edge list."""
    graph = [[] for _ in range(n)]
    for u, v in edges:
        graph[u].append(v)
        if not directed:
            graph[v].append(u)
    return graph

Drill 2: Count connected components

python
def count_components(n, edges):
    """Number of connected components in undirected graph."""
    graph = build_adj_list(n, edges, directed=False)
    visited = [False] * n
    count = 0
    for i in range(n):
        if not visited[i]:
            count += 1
            queue = deque([i])
            visited[i] = True
            while queue:
                u = queue.popleft()
                for v in graph[u]:
                    if not visited[v]:
                        visited[v] = True
                        queue.append(v)
    return count

Drill 3: Find all paths between two nodes (DFS backtracking)

python
def all_paths(graph, source, target):
    """All paths from source to target (LC 797)."""
    result = []
    def dfs(u, path):
        if u == target:
            result.append(path[:])
            return
        for v in graph[u]:
            path.append(v)
            dfs(v, path)
            path.pop()  # backtrack
    dfs(source, [source])
    return result
# Note: this is O(2^V * V) worst case — exponential!
# Only use when the graph is small or a DAG.

Drill 4: Check if path exists (simplest graph query)

python
def has_path(graph, source, target):
    """Does a path from source to target exist?"""
    visited = set([source])
    queue = deque([source])
    while queue:
        u = queue.popleft()
        if u == target:
            return True
        for v in graph[u]:
            if v not in visited:
                visited.add(v)
                queue.append(v)
    return False

Drill 5: Evaluate Division (LC 399, weighted graph DFS)

python
def calcEquation(equations, values, queries):
    """Given a/b=k, find a/c by DFS on weighted graph."""
    graph = {}
    for (a, b), v in zip(equations, values):
        graph.setdefault(a, []).append((b, v))
        graph.setdefault(b, []).append((a, 1.0 / v))

    def dfs(src, dst, visited):
        if src not in graph or dst not in graph:
            return -1.0
        if src == dst:
            return 1.0
        visited.add(src)
        for neighbor, weight in graph[src]:
            if neighbor not in visited:
                result = dfs(neighbor, dst, visited)
                if result != -1.0:
                    return weight * result
        return -1.0

    return [dfs(a, b, set()) for a, b in queries]
# This is DFS on a weighted graph where edge weights are ratios.
# a/b = 2.0, b/c = 3.0 → a/c = 2.0 * 3.0 = 6.0
# The path a → b → c has accumulated weight 2.0 * 3.0.

Drill 6: Topological sort one-liner (for quick coding)

python
def topo_sort(graph):
    """Compact DFS topological sort."""
    visited, order = set(), []
    def dfs(u):
        visited.add(u)
        for v in graph.get(u, []):
            if v not in visited:
                dfs(v)
        order.append(u)
    for u in graph:
        if u not in visited:
            dfs(u)
    return order[::-1]
# 10 lines, O(V+E), handles disconnected DAGs.
# Missing: cycle detection. Add gray-set for that.

Complexity Cheat Sheet

Chapter 10: Connections

You now have the complete toolkit for elementary graph traversal. BFS for shortest paths, DFS for structural analysis, topological sort for ordering, SCCs for clustering. These are the foundation. Everything in the next three CLRS chapters builds directly on what you learned here.

What Comes Next

The Hierarchy of Graph Problems

Key Takeaways

A Final Word on Mastery

Knowing the algorithms is necessary but not sufficient. Mastery means three things:

Recognition: Given a problem, you immediately see the graph structure and know which algorithm to apply. This comes from solving 30-50 graph problems across different disguises (grids, strings, states, dependencies).

Implementation speed: You can write BFS, DFS, topological sort, and SCC detection from memory in under 5 minutes each. This comes from repeated practice — write each one 10 times until it is muscle memory.

Debugging intuition: When your graph code gives wrong answers, you know the five most likely bugs (wrong visited timing, missing disconnected component handling, wrong edge direction, recursion limit, representation mismatch). This comes from making each mistake once and remembering it.

CLRS Chapter 22 Exercises Worth Doing

These exercises from the textbook are frequently adapted into interview questions. Work through them by hand before looking at solutions.

Time Complexity Summary — The One Table

Every algorithm in this chapter runs in O(V + E) with adjacency lists. This is optimal — you must examine every vertex and every edge at least once. Here is the complete summary:

Beyond Chapter 22: Advanced Graph Topics

The Relationship Map

Here is how every concept in this lesson connects to every other concept:

Study Plan for Interview Prep

The Big Picture: Why Graph Algorithms Matter

Graphs are the most versatile data structure in computer science. Almost every real-world system can be modeled as a graph — and almost every interesting question about that system reduces to a graph algorithm you learned in this lesson. When you see "connections," "dependencies," "reachability," or "ordering" in a problem statement, your first thought should be: what is the graph, and which traversal do I need?

Parting Advice

The four algorithms in this chapter — BFS, DFS, topological sort, and SCC decomposition — are the building blocks of all graph algorithms. Every more advanced algorithm (Dijkstra, Bellman-Ford, Prim's, Kruskal's, Ford-Fulkerson, A*) is built on top of one or more of these primitives. Master them thoroughly before moving to Chapter 23.

In interviews, the most common failure mode is not knowing the algorithm — it is not recognizing the problem as a graph problem. Train your "graph detector": whenever you see relationships, dependencies, reachability, or ordering, think graph. Then the algorithm choice is mechanical.

"The world is a graph. Most problems are about traversal."
— Jon Kleinberg