Graph Traversal

A traversal is a walk with a memory

Your build tool must list every module that main depends on, directly or through other modules. The import graph has no cycles, so a tempting plan is to recursively follow every import from every module. No cycles means no infinite loop, so why keep track of anything?

Here is why. Picture 30 "diamonds" in a row. Module m0 imports two helpers, both helpers import m1, m1 imports two more helpers that both import m2, and so on up to m30:

      ┌─> a1 ─┐       ┌─> a2 ─┐
  m0 ─┤       ├─> m1 ─┤       ├─> m2  ···  m30
      └─> b1 ─┘       └─> b2 ─┘

That is 91 modules and 120 imports. The memoryless walk reaches m1 twice, m2 four times, and m30 along 2³⁰ = 1,073,741,824 different paths. In total it enters a module 4,294,967,293 times. Add one set that remembers which modules you have already entered, skip those, and the same walk enters 91 modules and looks at 120 imports.

That is the whole lesson in one sentence: a traversal is a walk that admits each node once. Every algorithm below is the same loop. Take a node from the frontier (the nodes found but not yet explored), look at its neighbors, and admit each neighbor the first time you see it. Admitting each node once is what keeps the cost at O(V + E). The shape of the frontier decides the order: a stack gives depth-first, a queue gives breadth-first. And the order decides what else you learn. Depth-first order tells you when a node is finished, which exposes cycles and dependency orders. Breadth-first order tells you distance.

This lesson builds on Graph Algorithms & Search, which covers modeling problems as graphs and choosing a representation. Here we use adjacency lists throughout. It also reuses the "seen" set from Foundation: Arrays & Strings and the call-stack picture of recursion from Advanced Recursion & Backtracking.

Before any move: name the nodes, the edges and the question

Graph problems rarely hand you a graph. They hand you a grid, a list of pairs, or a class with pointers. Before choosing a traversal, answer three questions out loud:

Direction is part of the edge. In Course Schedule, [1, 0] means "take 0 before 1", so the edge runs 0 → 1. Read the pair order off the statement every time, because another problem in the same family flips it.

When the input is a list of pairs, build an adjacency list: one list of neighbors per node.

def build_graph(n, edges, directed=False):
    graph = [[] for _ in range(n)]      # every node gets a list, even with no edges
    for u, v in edges:
        graph[u].append(v)
        if not directed:
            graph[v].append(u)
    return graph

graph = build_graph(6, [(0, 1), (0, 2), (1, 3), (2, 3), (3, 4)])
print(graph)   # [[1, 2], [0, 3], [0, 3], [1, 2, 4], [3], []]

Allocating all n lists up front matters. Node 5 has no edges, and a dictionary built only from the pairs would never hear of it. An undirected edge is stored twice, once from each end, so the lists hold 2E entries.

Grids are graphs whose neighbor lists you compute on the fly. The neighbors of (r, c) are (r + dr, c + dc) for each offset in ((1, 0), (-1, 0), (0, 1), (0, -1)), kept only if the cell is inside the grid and passes the problem's test ("is land", "is fresh").

Cost vocabulary. V is the number of nodes and E the number of edges. For an r × c grid, V = rc, and E is at most 2rc. Set and dictionary operations are expected O(1).

Move 1: Depth-first search, go deep then back up

Smell: you need everything reachable from a start, or a yes/no "is there a path from A to B?"

Here is the graph we just built. It has five connected nodes and one loner:

  0 ─── 1
  │     │
  2 ─── 3 ─── 4        5

Predict first: a depth-first search (DFS) from 0 tries neighbors in list order. Which node does it enter third? Does it ever enter 5?

The recursive version

def dfs_order(graph, start):
    visited = set()
    order = []

    def dfs(u):
        visited.add(u)              # mark on entry, before looking at neighbors
        order.append(u)             # pre-order: record on the way down
        for v in graph[u]:
            if v not in visited:
                dfs(v)

    dfs(start)
    return order

print(dfs_order(graph, 0))   # [0, 1, 3, 2, 4]

This trace comes from an instrumented run. The path column is the call stack: the nodes whose dfs call is still open.

Each node has two moments. It is entered on the way down and finished on the way back up, after everything below it is done. Recording at entry gives pre-order: [0, 1, 3, 2, 4]. Recording at finish gives post-order (finish order): [2, 4, 3, 1, 0]. Pre-order is enough for "what is reachable". Finish order drives Moves 4 and 5.

Why it works, and what it costs

It reaches everything reachable. Suppose some node reachable from the start were missed. Walk along a path from the start to it and stop at the first missed node. Its predecessor on the path was entered, and entering a node scans all of its neighbors, so the missed node would have been entered too. That is a contradiction.

It enters nothing twice. A node joins visited the moment it is entered, and dfs(v) is only called when v is not in visited.

So each reachable node is entered once and its neighbor list is scanned once. The total is O(V + E) time: the scans cover 2E list entries for an undirected graph, E for a directed one. Extra space is O(V) for visited, plus the call stack, which is as deep as the longest path DFS walks. On a straight line of V nodes, that is V frames.

⚠️ Mark on entry, not on exit. Move visited.add(u) below the loop and the edge 0–1 alone breaks it: dfs(0) calls dfs(1), which sees that 0 is not marked yet and calls dfs(0) again, until Python raises RecursionError.

Python's recursion ceiling

CPython stops recursion at 1,000 frames by default (sys.getrecursionlimit()). On a straight path of just 999 nodes, dfs_order raises RecursionError. sys.setrecursionlimit raises the ceiling, but whether the process has enough real stack behind it depends on the Python version and the platform. The portable fix is not to recurse. Keep the frontier in your own list:

def dfs_iterative(graph, start):
    visited = set()
    order = []
    stack = [start]
    while stack:
        u = stack.pop()
        if u in visited:
            continue                    # u was pushed more than once
        visited.add(u)
        order.append(u)
        for v in reversed(graph[u]):    # reversed, so neighbors pop in list order
            if v not in visited:
                stack.append(v)
    return order

print(dfs_iterative(graph, 0))   # [0, 1, 3, 2, 4]

This version marks a node when it is popped, not when it is pushed. So a node can sit in the stack several times, once for each neighbor that saw it before it was entered, and the continue throws the extra copies away. It visits in exactly the recursive pre-order, but the stack can hold up to O(E) entries rather than O(V). On a complete graph with 200 nodes, the stack peaked at 19,702 entries.

Why not mark on push, which keeps the stack at O(V)? Because then the order stops being depth-first. On [[1, 2], [2, 3], [], []], recursion visits 0, 1, 2, 3. Mark-on-push visits 0, 1, 3, 2: node 2 was claimed by 0, so 1 can no longer dive into it. That is fine when you only need the set of reachable nodes (Move 2 does exactly that). It is wrong when you need DFS structure, such as finish order or "is this node on the current path".

def dfs_finish_order(graph, start, visited):
    finished = []
    visited.add(start)
    stack = [(start, iter(graph[start]))]    # the current path, with a bookmark per node
    while stack:
        u, neighbors = stack[-1]
        for v in neighbors:                 # resumes where u left off
            if v not in visited:
                visited.add(v)
                stack.append((v, iter(graph[v])))
                break                        # go deeper first
        else:                                # u has no unvisited neighbors left
            stack.pop()
            finished.append(u)
    return finished

print(dfs_finish_order(graph, 0, set()))   # [2, 4, 3, 1, 0]

Your turn: run dfs_iterative(graph, 0) by hand. Write the stack after each of the first four pops. Which node gets pushed twice, and what happens to its second copy?

Move 2: Flood fill, one launch per region

Smell: "how many separate islands / groups / provinces?" or "how big is the largest one?"

LeetCode 200: Number of Islands gives a grid of "1" (land) and "0" (water). An island is a group of land cells joined up, down, left or right. Count the islands.

Predict first: a classmate counts land cells whose upper and left neighbors are both water (or off the grid), reasoning that each island has exactly one such "top-left corner". What does that give on this grid, and what is the right answer?

1 0 1
1 1 1

Fill, then count the launches

def num_islands(grid):
    rows, cols = len(grid), len(grid[0])
    seen = set()

    def fill(r, c):
        seen.add((r, c))
        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
                    and grid[nr][nc] == "1" and (nr, nc) not in seen):
                fill(nr, nc)

    islands = 0
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == "1" and (r, c) not in seen:
                fill(r, c)          # swallows the whole island
                islands += 1        # one launch = one island
    return islands

grid = [list(row) for row in ["11000", "11011", "00010", "01000"]]
print(num_islands(grid))   # 3

The outer loop scans the grid in reading order. Each launch starts at the first cell of an island that nothing has touched yet:

Why the count is right. Before each step of the outer loop, every land cell is either in seen together with its whole island, or its island is untouched. A launch therefore happens exactly once per island: at that island's first cell in reading order. Each cell is entered once and checks four neighbors, so the cost is O(rows · cols) time. Extra space is O(rows · cols) for seen plus the recursion.

The same shape counts components of any graph. Only the neighbor generation changes. Launch only once, from the first land cell, and you count one island. Drop the not in seen test in the outer loop and you count land cells.

Traps that cost submissions

⚠️ Check bounds before you index. In Python, grid[-1][c] does not raise an error; it silently reads the last row. And grid[rows][c] raises IndexError. The condition 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == "1" works because and stops at the first false part, so the grid is only indexed once the cell is known to be inside. Write the out-of-bounds test as nr < 0 or nr >= rows. With nr > rows, the value nr == rows slips through and crashes.

⚠️ Sinking the island is a contract decision. Many solutions skip seen and write grid[r][c] = "0" instead. That saves the set but destroys the caller's grid. LeetCode 200 accepts it. A caller who needs the grid afterwards does not. Either way, the recursion or stack is still O(rows · cols) in the worst case, so sinking does not make the traversal O(1) space.

⚠️ Recursion depth is the island's size, not its width. On an all-land 300 × 300 grid (the size LeetCode 200 allows), fill recurses 90,000 deep: the fill snakes through every cell before returning once. Under stock Python, num_islands already fails at 32 × 32 (1,024 cells). An explicit stack avoids that. Here, marking on push is fine, because only the set of cells matters:

def num_islands_iterative(grid):
    rows, cols = len(grid), len(grid[0])
    seen = set()
    islands = 0
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] != "1" or (r, c) in seen:
                continue
            islands += 1
            seen.add((r, c))
            stack = [(r, c)]
            while stack:
                cr, cc = stack.pop()
                for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
                    nr, nc = cr + dr, cc + dc
                    if (0 <= nr < rows and 0 <= nc < cols
                            and grid[nr][nc] == "1" and (nr, nc) not in seen):
                        seen.add((nr, nc))      # mark on push: fine for "which cells"
                        stack.append((nr, nc))
    return islands

print(num_islands_iterative([["1"] * 300 for _ in range(300)]))   # 1

The same move on an edge list

"There are n nodes and a list of undirected edges; how many connected components?" is the same algorithm. The outer loop must run over all n nodes, because a node with no edges is a component of its own:

def count_components(n, edges):
    graph = build_graph(n, edges)
    seen = set()
    count = 0
    for s in range(n):                  # every node, including ones with no edges
        if s in seen:
            continue
        count += 1
        seen.add(s)
        stack = [s]
        while stack:
            u = stack.pop()
            for v in graph[u]:
                if v not in seen:
                    seen.add(v)
                    stack.append(v)
    return count

print(count_components(6, [(0, 1), (0, 2), (1, 3), (2, 3), (3, 4)]))   # 2

The answer is 2: {0, 1, 2, 3, 4} and the lonely {5}. Loop over the keys of a dictionary built from the edges instead, and node 5 is never counted. LeetCode 547: Number of Provinces asks the same question with an adjacency matrix as input. (Union-find, from Graph Algorithms & Search, is the other standard tool for counting components, especially when edges arrive one at a time.)

Your turn: LeetCode 695: Max Area of Island uses integer cells 1/0 and asks for the size of the largest island, or 0 if there is none. Change the fill so it returns the size of what it swallowed. What should it return for [[1, 1, 0, 0], [1, 0, 0, 1], [0, 1, 1, 1]]?

def max_area_of_island(grid):
    rows, cols = len(grid), len(grid[0])

    def area(r, c):
        if not (0 <= r < rows and 0 <= c < cols) or grid[r][c] != 1:
            return 0
        grid[r][c] = 0                  # sink it: marks visited by changing the input
        return 1 + area(r + 1, c) + area(r - 1, c) + area(r, c + 1) + area(r, c - 1)

    return max(area(r, c) for r in range(rows) for c in range(cols))

print(max_area_of_island([[1, 1, 0, 0], [1, 0, 0, 1], [0, 1, 1, 1]]))   # 4

Move 3: Breadth-first search, ripples give distances

Smell: "fewest moves", "minimum steps", "how many minutes until…", where every move costs the same.

Predict first: a teammate runs DFS on the 5-cycle 0–1–2–3–4–0 from node 0. They store the depth at which each node was first entered and call it the distance. The adjacency lists are [[1, 4], [0, 2], [1, 3], [2, 4], [3, 0]]. What do they record for node 4, and what is the real distance?

The queue version

Breadth-first search (BFS) keeps the frontier in a FIFO queue. The start comes out first, then everything one edge away, then everything two edges away, like ripples from a stone.

from collections import deque

def bfs_distances(graph, source):
    dist = {source: 0}              # doubles as the visited set
    queue = deque([source])
    while queue:
        u = queue.popleft()
        for v in graph[u]:
            if v not in dist:       # first discovery = fewest edges
                dist[v] = dist[u] + 1
                queue.append(v)
    return dist

print(bfs_distances(graph, 0))   # {0: 0, 1: 1, 2: 1, 3: 2, 4: 3}

On the Move 1 graph from node 0:

Node 5 is missing from dist because it is unreachable. Check for that before you read dist[target].

Why the first discovery is the shortest

Invariant: the queue always holds nodes in non-decreasing distance order, and its front and back differ by at most 1. It starts as [source]. Popping a node at distance d appends nodes at distance d + 1 to the back, which keeps the invariant true. So every node at distance d is popped before any node at distance d + 1.

Now take a node v whose true distance is d + 1. One of its neighbors, u, sits at distance d. That u is popped before any node at distance d + 1, so v is discovered no later than from u, and gets label d + 1. A smaller label would need a neighbor closer than d, and v has none. Hence first discovery = fewest edges, in any graph where every edge counts as 1. For weighted edges, see Shortest Path Algorithms.

Cost: each node is enqueued once and its list scanned once, so O(V + E) time and O(V) extra space.

When to mark: three versions of one loop

Where you mark a node as visited changes the cost, and in one case the cost explodes. All numbers below come from real runs:

The third version is the classic beginner loop: u = queue.popleft(); visited.add(u), then push every unvisited neighbor. The second version is the same loop with if u in visited: continue right after the pop. Two neighbors that both see an unmarked cell both push it, each copy is expanded, and the copies multiply layer by layer. It never loops forever, since a node that is marked is never pushed again, but it can take exponential time. Mark on enqueue and the problem cannot arise.

⚠️ Use deque, not list.pop(0). pop(0) shifts every remaining element left, so it costs O(length of the queue). A BFS whose queue grows to about V entries then costs O(V²). A star graph does exactly that. In one run on a laptop, a star with 100,000 nodes took 0.74 s with a list and 0.008 s with a deque. Doubling to 200,000 nodes made the list version about four times slower (2.9 s), which is the quadratic signature. deque.popleft() is O(1).

Many sources at once: Rotting Oranges

LeetCode 994: Rotting Oranges: cells are 0 (empty), 1 (fresh) or 2 (rotten). Every minute, each rotten orange rots its fresh 4-neighbors. Return the minutes until no fresh orange is left, or −1 if some can never rot.

The slow approach simulates minute by minute, rescanning the whole grid each time: O((rows·cols)²) in the worst case. The fast approach sees that every orange's rotting time is its BFS distance to the nearest rotten orange. Put all rotten oranges in the queue at distance 0 and run one BFS. This is multi-source BFS. It is the same as adding an imaginary start node joined to every source, so the queue invariant and the proof still hold.

def oranges_rotting(grid):
    rows, cols = len(grid), len(grid[0])
    queue = deque()
    fresh = 0
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == 2:
                queue.append((r, c))        # every rotten orange starts at minute 0
            elif grid[r][c] == 1:
                fresh += 1
    minutes = 0
    while queue and fresh:
        minutes += 1                        # one full level = one minute
        for _ in range(len(queue)):         # snapshot: only this minute's sources
            r, c = 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 and grid[nr][nc] == 1:
                    grid[nr][nc] = 2        # mark on enqueue
                    fresh -= 1
                    queue.append((nr, nc))
    return minutes if fresh == 0 else -1

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

for _ in range(len(queue)) is the level snapshot. It processes exactly the oranges that rotted in the previous minute (the initially rotten ones in minute 1). The ones it rots join the back of the queue and wait for the next minute.

⚠️ The last level rots nothing. Write while queue: instead of while queue and fresh: and the loop runs once more, for the oranges that rotted in minute 4. It returns 5 here, and 1 instead of 0 for [[0, 2]], where nothing is fresh at all. Test three edge cases every time: no fresh oranges (answer 0), a fresh orange with no rotten one anywhere (−1), and a fresh orange walled off by empty cells (−1).

Cost: each cell is enqueued at most once, so the run takes O(rows · cols) time and O(rows · cols) queue space. It also mutates grid, which LeetCode allows.

Your turn: LeetCode 1091: Shortest Path in Binary Matrix. An n × n grid of 0 (open) and 1 (blocked). Return the number of cells on the shortest path from the top-left to the bottom-right corner, moving in 8 directions (diagonals count), or −1 if there is none. Predict the answer for [[0, 0, 0], [1, 1, 0], [1, 1, 0]] and for [[0, 1], [1, 0]]. Which two details differ from bfs_distances?

def shortest_path_binary_matrix(grid):
    n = len(grid)
    if grid[0][0] == 1 or grid[n - 1][n - 1] == 1:
        return -1
    dist = {(0, 0): 1}                      # the path length counts cells, so start at 1
    queue = deque([(0, 0)])
    while queue:
        r, c = queue.popleft()
        if (r, c) == (n - 1, n - 1):
            return dist[(r, c)]
        for dr in (-1, 0, 1):
            for dc in (-1, 0, 1):           # 8 directions; (0, 0) is caught by dist
                nr, nc = r + dr, c + dc
                if (0 <= nr < n and 0 <= nc < n and grid[nr][nc] == 0
                        and (nr, nc) not in dist):
                    dist[(nr, nc)] = dist[(r, c)] + 1
                    queue.append((nr, nc))
    return -1

print(shortest_path_binary_matrix([[0, 0, 0], [1, 1, 0], [1, 1, 0]]))   # 4
print(shortest_path_binary_matrix([[0, 1], [1, 0]]))                    # 2

DFS or BFS?

Both run in O(V + E) and both need a visited structure. Choose by the question, not by speed:

The memory shapes differ too. Recursive DFS holds the current path, which is V deep on a long chain. BFS holds a frontier, which is V − 1 wide after the center of a star. Both are O(V) in the worst case.

Move 4: Cycles, and why directed graphs need a third color

Smell: "can all courses be finished?", "is there a circular dependency?", "is this graph a tree?"

LeetCode 207: Course Schedule asks whether you can take all numCourses courses, given pairs [a, b] meaning "take b before a". You can finish everything exactly when the prerequisite graph has no directed cycle.

Predict first: this detector says "I reached a node I have seen before, so I went round a loop". Does it work on the diamond 0 → 1, 0 → 2, 1 → 3, 2 → 3?

def has_cycle_wrong(graph):
    visited = set()

    def dfs(u):
        if u in visited:
            return True                 # "seen before, so we went round a loop"
        visited.add(u)
        return any(dfs(v) for v in graph[u])

    return any(dfs(u) for u in range(len(graph)))

Three colors

Give each node one of three states:

• WHITE: not entered yet.
• GRAY: entered but not finished. It is on the current recursion path.
• BLACK: finished. Everything reachable from it has been explored.

WHITE, GRAY, BLACK = 0, 1, 2

def has_cycle(graph):                       # directed graph as adjacency lists
    color = [WHITE] * len(graph)

    def dfs(u):
        color[u] = GRAY                     # u is on the current path
        for v in graph[u]:
            if color[v] == GRAY:
                return True                 # an edge back into the current path
            if color[v] == WHITE and dfs(v):
                return True
        color[u] = BLACK                    # u is finished: no cycle through it
        return False

    return any(color[u] == WHITE and dfs(u) for u in range(len(graph)))

print(has_cycle([[1], [2], [3], [1]]))          # True: 1 -> 2 -> 3 -> 1
print(has_cycle([[1, 2], [3], [3], []]))        # False: the diamond

Trace of the first call, edges 0 → 1 → 2 → 3 → 1:

Node 0 is on the path but not on the cycle. The cycle is the part of the path from the GRAY node onward.

Why GRAY means cycle, and only then. The GRAY nodes are exactly the open calls, so they form a path. An edge u → v with v GRAY therefore leads back to an ancestor of u, and the path from v to u plus that edge is a cycle. Conversely, suppose a cycle exists, and let v be the first of its nodes that DFS enters. At that moment the rest of the cycle is WHITE and reachable from v, so DFS cannot finish v without walking around to the cycle node w that points back to v. When w examines w → v, v is still GRAY. A BLACK neighbor is harmless: it is already finished, either a shared descendant like node 3 in the diamond or a node finished in an earlier search.

Cost: O(V + E) time, and O(V) for the colors plus the recursion.

Undirected graphs are different

In an undirected adjacency list, every edge appears from both ends. Run has_cycle on the plain path 0 – 1 – 2, and at node 1 it sees 0, which is GRAY, and reports a cycle. It prints True for a graph that is a tree. The fix is to ignore the edge you arrived on:

def has_cycle_undirected(graph):            # undirected graph as adjacency lists
    seen = set()

    def dfs(u, parent):
        seen.add(u)
        for v in graph[u]:
            if v == parent:
                continue                    # the edge we arrived on
            if v in seen or dfs(v, u):
                return True
        return False

    return any(u not in seen and dfs(u, -1) for u in range(len(graph)))

print(has_cycle_undirected(build_graph(3, [(0, 1), (1, 2)])))           # False
print(has_cycle_undirected(build_graph(3, [(0, 1), (1, 2), (2, 0)])))   # True

In undirected DFS, any already-seen neighbor other than the parent closes a loop. Two states (seen or not) are enough here because, without arrows, the diamond from the prediction above is a cycle: 0–1–3–2–0. Directed graphs need GRAY to tell "on my path" apart from "finished elsewhere". It even catches a doubled edge. The child skips both copies of the edge back to its parent, but the parent's own list holds the child twice, and the second copy finds the child already seen.

Your turn: "Given n nodes and an undirected edge list, is it a tree?" (LeetCode 261: Graph Valid Tree is premium, but the question is classic). Someone checks only len(edges) == n - 1. Give an input that fools them, and a correct test that reuses code you already have.

def valid_tree(n, edges):
    return len(edges) == n - 1 and count_components(n, edges) == 1

Course Schedule, finished

def can_finish(num_courses, prerequisites):
    graph = [[] for _ in range(num_courses)]
    for course, pre in prerequisites:
        graph[pre].append(course)           # pre must come first: pre -> course
    return not has_cycle(graph)

print(can_finish(2, [[1, 0]]))              # True
print(can_finish(2, [[1, 0], [0, 1]]))      # False

Two things to know before you submit:

• Direction does not change this answer. Reversing every edge turns a cycle into a reversed cycle, so can_finish gives the same result either way (checked on 3,000 random inputs). It does change Move 5's answer: a reversed graph yields a reversed order.
• Depth. LeetCode 207 allows 2,000 courses. A chain of 2,000 courses makes this recursion 2,000 calls deep, past stock Python's limit. Kahn's algorithm (next) uses no recursion at all.

Move 5: Topological order, schedule the dependencies

Smell: "return an order", "valid build/install sequence", with before/after constraints. LeetCode 210: Course Schedule II wants any order that puts every prerequisite before its course, or [] if none exists.

A topological order lists the nodes so that every edge u → v has u before v. It exists exactly when the graph has no directed cycle, and there are usually several. We will use five courses, with course 4 hanging off to the side:

      ┌──> 1 ──┐
  0 ──┤        ├──> 3 <── 4
      └──> 2 ──┘

prerequisites = [[1, 0], [2, 0], [3, 1], [3, 2], [3, 4]]

Way 1: reverse the finish order

When a node finishes in DFS, everything it leads to has already finished. So the finish order lists every course after all the courses that depend on it. Reverse it and you have a schedule. The GRAY check from Move 4 comes along for free:

def find_order(num_courses, prerequisites):
    graph = [[] for _ in range(num_courses)]
    for course, pre in prerequisites:
        graph[pre].append(course)
    color = [WHITE] * num_courses
    finished = []                           # post-order

    def dfs(u):
        color[u] = GRAY
        for v in graph[u]:
            if color[v] == GRAY:
                return False                # cycle: no valid order
            if color[v] == WHITE and not dfs(v):
                return False
        color[u] = BLACK
        finished.append(u)                  # everything u leads to is already here
        return True

    for u in range(num_courses):
        if color[u] == WHITE and not dfs(u):
            return []
    return finished[::-1]                   # reverse post-order

prereqs = [[1, 0], [2, 0], [3, 1], [3, 2], [3, 4]]
print(find_order(5, prereqs))   # [4, 0, 2, 1, 3]

Reversed, that gives [4, 0, 2, 1, 3].

Why it works. Take any edge u → v. When u examines v, v is WHITE, BLACK, or GRAY. If WHITE, v is explored and finished inside u's call, so before u finishes. If BLACK, v finished earlier still. GRAY is impossible when there is no cycle. So v always finishes before u. In the reversed list, u comes before v.

⚠️ One start is not enough. Run DFS only from 0 and you get [0, 2, 1, 3]. It is a fine order for what 0 reaches, but course 4, which must precede 3, is missing. The outer loop over every node is what makes the order complete.

Way 2: Kahn's algorithm, peel off what is ready

Count each course's unplaced prerequisites (its in-degree). Any course at 0 is ready. Place a ready course, and each course that depended on it loses one prerequisite. Whatever drops to 0 becomes ready in turn.

def find_order_kahn(num_courses, prerequisites):
    graph = [[] for _ in range(num_courses)]
    indegree = [0] * num_courses            # prerequisites not yet placed
    for course, pre in prerequisites:
        graph[pre].append(course)
        indegree[course] += 1
    queue = deque(u for u in range(num_courses) if indegree[u] == 0)
    order = []
    while queue:
        u = queue.popleft()
        order.append(u)
        for v in graph[u]:
            indegree[v] -= 1
            if indegree[v] == 0:            # v's last prerequisite was just placed
                queue.append(v)
    return order if len(order) == num_courses else []

print(find_order_kahn(5, prereqs))   # [0, 4, 1, 2, 3]

The in-degrees start as [0, 1, 1, 3, 0], so the queue starts as [0, 4]:

Why it works. Invariant: indegree[v] counts v's prerequisites not yet in order. A course enters the queue exactly when that count reaches 0, so it is placed only after all its prerequisites. If there is a cycle, no course on it can ever reach 0, because each one waits for the one before it. Those courses are never placed, and len(order) < num_courses reports the cycle. If there is no cycle, some unplaced course always has in-degree 0. (If none did, you could walk backwards from prerequisite to prerequisite forever, and in a finite graph you would repeat a course, which would be a cycle.) So every course gets placed.

Both ways cost O(V + E) time and O(V + E) extra space, most of it the adjacency list they build; beyond that list they need O(V). Kahn's has no recursion, detects the cycle with one length check, and gives the lexicographically smallest valid order if you swap the queue for a min-heap (see Heaps & Priority Queues). The DFS way reuses the three-color code and suits problems that already walk the graph depth-first.

Test it like a professional

The two methods return different valid orders ([4, 0, 2, 1, 3] and [0, 4, 1, 2, 3]), so comparing outputs with == proves nothing. Check the property instead, and compare against brute force on tiny inputs:

import itertools, random

def is_valid_order(order, num_courses, prerequisites):
    position = {course: i for i, course in enumerate(order)}
    return (sorted(order) == list(range(num_courses))
            and all(position[pre] < position[course] for course, pre in prerequisites))

def order_exists(num_courses, prerequisites):          # brute force for tiny n
    return any(is_valid_order(list(p), num_courses, prerequisites)
               for p in itertools.permutations(range(num_courses)))

def check(trials=500):
    for _ in range(trials):
        n = random.randint(1, 6)
        pairs = {(random.randrange(n), random.randrange(n)) for _ in range(random.randint(0, 8))}
        prereqs = [[a, b] for a, b in pairs if a != b]
        for solver in (find_order, find_order_kahn):
            order = solver(n, prereqs)
            if order_exists(n, prereqs):
                assert is_valid_order(order, n, prereqs), (n, prereqs, order)
            else:
                assert order == [], (n, prereqs, order)
    print("all matched")

check()   # all matched

Your turn: run Kahn's on num_courses = 4, prerequisites = [[1, 0], [2, 1], [1, 2], [3, 0]]. What does order hold when the queue empties, what is returned, and why is course 1 stuck?

Move 6: Two colors, the bipartite check

Smell: "split into two groups so that every conflict (dislike, edge) goes between the groups."

LeetCode 785: Is Graph Bipartite? gives an undirected graph as adjacency lists, possibly disconnected. Can the nodes be colored with two colors so that every edge joins different colors?

def is_bipartite(graph):
    color = [-1] * len(graph)               # -1 = not colored yet
    for s in range(len(graph)):             # the graph may be disconnected
        if color[s] != -1:
            continue
        color[s] = 0
        queue = deque([s])
        while queue:
            u = queue.popleft()
            for v in graph[u]:
                if color[v] == -1:
                    color[v] = 1 - color[u]     # forced: the opposite of u
                    queue.append(v)
                elif color[v] == color[u]:
                    return False                # an edge inside one group
    return True

print(is_bipartite([[1, 2, 3], [0, 2], [0, 1, 3], [0, 2]]))   # False
print(is_bipartite([[1, 3], [0, 2], [1, 3], [0, 2]]))         # True

In the first graph, popping 0 colors 1, 2 and 3 all with color 1. Popping 1 then finds its neighbor 2 also colored 1: the edge 1–2 sits inside one group. Triangles such as 0–1–2 are to blame. The second graph is a square, and it alternates cleanly.

Why it works. Inside one connected component, the first color is a free choice, and every other color is forced: a node must get the opposite of the neighbor that discovered it. So if the forced coloring puts an edge inside one group, no two-coloring exists. If every edge has been checked and none conflicts, the coloring is a valid answer. Another way to say it: a graph is bipartite exactly when it has no odd cycle. Going round a cycle alternates colors, so an odd cycle comes back to its start with the wrong color.

⚠️ Color every component. Start only from node 0 and a triangle elsewhere goes unchecked. On build_graph(5, [(0, 1), (2, 3), (3, 4), (4, 2)]), a version without the outer loop returns True; the real answer is False. DFS colors just as well as BFS. Either way the cost is O(V + E) time and O(V) extra space.

Your turn: LeetCode 886: Possible Bipartition. People are labeled 1 to n, and dislikes[i] = [a, b] means a and b must go to different groups. Reuse is_bipartite. What do you get for n = 4, dislikes = [[1, 2], [1, 3], [2, 4]] and for n = 3, dislikes = [[1, 2], [1, 3], [2, 3]]?

def possible_bipartition(n, dislikes):
    graph = [[] for _ in range(n + 1)]      # people are 1..n; slot 0 stays empty
    for a, b in dislikes:
        graph[a].append(b)
        graph[b].append(a)
    return is_bipartite(graph)

print(possible_bipartition(4, [[1, 2], [1, 3], [2, 4]]))   # True
print(possible_bipartition(3, [[1, 2], [1, 3], [2, 3]]))   # False

Move 7: Clone Graph, traversal plus an old→new map

Smell: "return a deep copy" of something whose pointers can form cycles.

LeetCode 133: Clone Graph gives one node of a connected undirected graph. Each Node has a val and a list neighbors. Return a copy in which no node is shared with the original.

A copy needs one new node per original node, and every edge must point at the copies. When you meet a node for the second time, you must return the copy you already made, not a new one. So you need a map from each original node to its copy. That map is also the visited set.

class Node:
    def __init__(self, val=0, 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 = {}                             # original node -> its copy

    def copy(u):
        if u in copies:
            return copies[u]
        twin = Node(u.val)
        copies[u] = twin                    # register BEFORE visiting neighbors
        for v in u.neighbors:
            twin.neighbors.append(copy(v))
        return twin

    return copy(node)

a, b, c, d = Node(1), Node(2), Node(3), Node(4)             # the square 1-2-3-4-1
a.neighbors, b.neighbors, c.neighbors, d.neighbors = [b, d], [a, c], [b, d], [a, c]
twin = clone_graph(a)
print(twin is a, [n.val for n in twin.neighbors], twin.neighbors[0].neighbors[0] is twin)   # False [2, 4] True

The last check matters. Going from the copy of 1 to the copy of 2 and back lands on the same copy of 1. The copy has the square's shape, not just its values.

Why the registration line comes first. Copying 1 leads to copying 2, which looks at 2's neighbor 1. If 1 were registered only after its loop, copy(1) would start again, then copy(2) again, and so on until RecursionError. Registering first is Move 1's rule, "mark on entry", in a new costume.

Key the map by the node object itself. Python's default __hash__ for a class like Node uses identity, so two different nodes that happen to share a value never collide. LeetCode 133 promises unique values, so keying by val passes there, but the object key is correct in general.

Cost: O(V + E) time. Extra space is O(V) for the map plus the recursion, not counting the copy itself, which is the output (V nodes and E-sized neighbor lists).

Your turn: write the BFS version. When should a copy be created, and when should an edge be added?

def clone_graph_bfs(node):
    if node is None:
        return None
    copies = {node: Node(node.val)}
    queue = deque([node])
    while queue:
        u = queue.popleft()
        for v in u.neighbors:
            if v not in copies:
                copies[v] = Node(v.val)     # create on discovery = mark on enqueue
                queue.append(v)
            copies[u].neighbors.append(copies[v])
    return copies[node]

Final round: no label on the problem

Real problems do not say "use BFS". Name the nodes, the edges and the question, find the smell, and then pick the move.

Challenge 1: distance to the nearest zero

LeetCode 542: 01 Matrix. Given a grid of 0s and 1s (at least one 0, up to 10⁴ cells), return a grid where each cell holds the number of 4-directional steps to the nearest 0. For [[0, 0, 0], [0, 1, 0], [1, 1, 1]] the answer is [[0, 0, 0], [0, 1, 0], [1, 2, 1]].

1. What does the slow version repeat?
2. Which move applies, and where does the queue start?

def update_matrix(mat):
    rows, cols = len(mat), len(mat[0])
    dist = [[-1] * cols for _ in range(rows)]
    queue = deque()
    for r in range(rows):
        for c in range(cols):
            if mat[r][c] == 0:
                dist[r][c] = 0
                queue.append((r, c))        # every 0 is a source
    while queue:
        r, c = 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 and dist[nr][nc] == -1:
                dist[nr][nc] = dist[r][c] + 1
                queue.append((nr, nc))
    return dist

print(update_matrix([[0, 0, 0], [0, 1, 0], [1, 1, 1]]))   # [[0, 0, 0], [0, 1, 0], [1, 2, 1]]

Challenge 2: capture the surrounded regions

LeetCode 130: Surrounded Regions. A board of "X" and "O". Flip every "O" region that does not touch the border to "X", in place. ["XXXX", "XOOX", "XXOX", "XOXX"] becomes ["XXXX", "XXXX", "XXXX", "XOXX"]: the bottom O touches the border and survives.

Which cells are easy to classify, and which move finds the rest?

def solve_surrounded(board):
    rows, cols = len(board), len(board[0])
    stack = [(r, c) for r in range(rows) for c in range(cols)
             if (r in (0, rows - 1) or c in (0, cols - 1)) and board[r][c] == "O"]
    for r, c in stack:
        board[r][c] = "S"                   # safe: touches the border
    while stack:
        r, c = stack.pop()
        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 and board[nr][nc] == "O":
                board[nr][nc] = "S"
                stack.append((nr, nc))
    for r in range(rows):
        for c in range(cols):
            board[r][c] = "O" if board[r][c] == "S" else "X"

board = [list(row) for row in ["XXXX", "XOOX", "XXOX", "XOXX"]]
solve_surrounded(board)
print(["".join(row) for row in board])   # ['XXXX', 'XXXX', 'XXXX', 'XOXX']

Challenge 3: many "is it a prerequisite?" questions

LeetCode 1462: Course Schedule IV. There are numCourses ≤ 100 courses and an acyclic list prerequisites, where [a, b] means a must be taken before b. Then come up to 10⁴ queries [u, v]: is u a prerequisite of v, directly or indirectly? Return a list of booleans.

1. Which direction do the edges point this time?
2. With 100 courses and 10⁴ queries, what should you compute once?

def check_if_prerequisite(num_courses, prerequisites, queries):
    graph = [[] for _ in range(num_courses)]
    for a, b in prerequisites:
        graph[a].append(b)                  # here [a, b] means a BEFORE b
    reach = []
    for s in range(num_courses):            # one traversal per course
        seen = set()                        # courses reachable from s by >= 1 edge
        stack = [s]
        while stack:
            u = stack.pop()
            for v in graph[u]:
                if v not in seen:
                    seen.add(v)
                    stack.append(v)
        reach.append(seen)
    return [v in reach[u] for u, v in queries]

print(check_if_prerequisite(3, [[1, 2], [1, 0], [2, 0]], [[1, 0], [1, 2]]))   # [True, True]
print(check_if_prerequisite(2, [[1, 0]], [[0, 1], [1, 0]]))                   # [False, True]

Cheat sheet: smell → move

Before moving on, pick one problem from this lesson and solve it aloud from a blank editor. Say what the nodes and edges are and which way the edges point. Say what the frontier holds and when a node is marked. Explain why the answer is correct: which invariant holds, and what a GRAY node or a queue level means at that moment. Give the cost, including the recursion stack. Then name the change that would break it: weighted edges, a disconnected input, a 300 × 300 grid under Python's recursion limit. If you can do that, the graph lessons that follow build on these seven moves.

Next: Shortest Path Algorithms for weighted edges (Dijkstra), Word Ladder and other state-space searches. Graph Algorithms & Search covers union-find, the other way to count components. Binary Tree Patterns covers level-order and depth-first traversal on trees.