Depth-First Search — exercises

WHITE, GRAY, BLACK = 0, 1, 2

def has_cycle(graph):
    color = {v: WHITE for v in graph}
    def visit(u):
        color[u] = GRAY
        for v in graph.get(u, []):
            if color.get(v, WHITE) == GRAY: return True
            if color.get(v, WHITE) == WHITE and visit(v): return True
        color[u] = BLACK
        return False
    return any(color[u] == WHITE and visit(u) for u in graph)

print(has_cycle({'A': ['B'], 'B': ['C'], 'C': ['A']}))     # True
print(has_cycle({'A': ['B', 'C'], 'B': ['C'], 'C': []}))   # False

(a) Has cycle. Starting DFS at $A$: color $A$ gray, visit $B$ (gray), visit $C$ (gray), look at $C\to A$ — $A$ is gray, cycle detected.

(b) No cycle. Starting at $A$: visit $B$, visit $C$ (no neighbors), finish $C$ (black), finish $B$ (black), explore $A\to C$ — $C$ already black, not a back edge. Finish $A$.

The three-color scheme is the substrate for cycle detection. In undirected graphs it's simpler: any edge to a non-parent visited vertex is a back edge.

Run DFS, record finish times: e.g., $d[A]=1,f[E]=4,f[D]=5,f[B]=6,f[C]=8,f[A]=9$ (one valid trace). Sorting by decreasing finish: $A,C,B,D,E$. ✓ Valid topo order.

def topo_sort(graph):
    visited = set()
    order = []
    def visit(u):
        visited.add(u)
        for v in graph[u]:
            if v not in visited: visit(v)
        order.append(u)              # post-order push
    for u in graph:
        if u not in visited: visit(u)
    return list(reversed(order))     # reverse for topo order

print(topo_sort({'A': ['B', 'C'], 'B': ['D'], 'C': ['D'], 'D': ['E'], 'E': []}))
# ['A', 'C', 'B', 'D', 'E']  (one of several valid orders)

Why this works: for any edge $u\to v$, $v$ is either visited within $u$'s DFS subtree (so $f[v]<f[u]$) or visited entirely before $u$ in some earlier outer-loop call (so $f[v]<d[u]<f[u]$). Either way $f[u]>f[v]$. Decreasing finish-time order respects all such edges.

If the graph has a cycle, no topological order exists — and indeed the three-color cycle detection from P.1 catches this case during DFS.

3 components: $\{1,2,3\},\{4,5\},\{6\}$.

def count_components(graph):
    visited = set()
    count = 0
    def visit(u):
        visited.add(u)
        for v in graph[u]:
            if v not in visited: visit(v)
    for u in graph:
        if u not in visited:
            visit(u)
            count += 1
    return count

g = {1: [2, 3], 2: [1], 3: [1], 4: [5], 5: [4], 6: []}
print(count_components(g))    # 3

This is the pattern for any "do DFS, count something per starting vertex" problem. Same loop structure also handles: counting weakly connected components in directed graphs (after symmetrizing), counting connected groups of like-colored cells in an image (treating each 1-cell as a vertex), counting "islands" in a grid.

Preorder (root, left, right): 1, 2, 4, 5, 3, 6. Used to copy a tree (visit root first so you can build the new tree's root before recursing).

Inorder (left, root, right): 4, 2, 5, 1, 6, 3. On a binary search tree, gives sorted order. Used for tree-to-sorted-array conversion.

Postorder (left, right, root): 4, 5, 2, 6, 3, 1. Used to delete a tree (free children before parent) or compute aggregate values (height, size — anything that needs children's values to compute the parent's).

All three are the same DFS skeleton:

def traverse(node, out, order):
    if not node: return
    if order == 'pre':  out.append(node.val)
    traverse(node.left, out, order)
    if order == 'in':   out.append(node.val)
    traverse(node.right, out, order)
    if order == 'post': out.append(node.val)

Choice of order depends on what the algorithm needs to know about its children before processing itself.

Simple DFS reachability:

def reachable(graph, src, target):
    visited = set()
    def visit(u):
        if u == target: return True
        visited.add(u)
        return any(v not in visited and visit(v) for v in graph[u])
    return visit(src)

Using the timestamps from the worked example: $d[B]=2,f[B]=9$. $d[F]=6,f[F]=7$. $[6,7]\subset [2,9]$, so $F$ is in $B$'s DFS subtree. Yes, $F$ is reachable from $B$.

$d[C]=10,f[C]=11$. $[10,11]$ is disjoint from $[2,9]$ — they don't nest. So $C$ is not a descendant of $B$ in the DFS tree. No, $C$ is not reachable from $B$ (you can verify by looking at the edge list — there's no path from $B$ back to $C$).

Caveat: nesting timestamps give reachability within the DFS tree. For non-tree edges (cross edges, forward edges), you need to check the edge directly. In directed graphs, the timestamp test is necessary but not sufficient for general reachability — it captures DFS-tree ancestry, which is a subset.

One valid path: D, R, R, D, D, R from (0,0) to (3,3). Trace: (0,0) → (1,1)? No, (0,1)... actually we have to navigate around walls.

Path: (0,0) → (0,1) → (1,1) → (2,1) → (2,0) — wait this is going backward. Let me trace more carefully.

Walls at (0,2), (1,0), (1,2), (3,1), (3,2). Open cells form a connected region. One path: (0,0) → (0,1) → (1,1) → (2,1) → (2,2) → (2,3) → (3,3). Moves: R, D, D, R, R, D.

def maze_path(maze):
    m, n = len(maze), len(maze[0])
    visited = [[False]*n for _ in range(m)]
    path = []
    def visit(i, j):
        if i == m-1 and j == n-1:
            path.append((i, j))
            return True
        visited[i][j] = True
        path.append((i, j))
        for di, dj in [(1,0),(0,1),(-1,0),(0,-1)]:
            ni, nj = i+di, j+dj
            if 0 <= ni < m and 0 <= nj < n and maze[ni][nj] == 0 and not visited[ni][nj]:
                if visit(ni, nj): return True
        path.pop()                       # ← backtrack
        return False
    visit(0, 0)
    return path

maze = [[0,0,1,0],[1,0,1,0],[0,0,0,0],[0,1,1,0]]
print(maze_path(maze))   # Some valid path

Backtracking is the canonical DFS application: when a path doesn't pan out, undo the most recent choice and try the next one. The same pattern is the engine behind N-queens, Sudoku solvers, constraint satisfaction, and combinatorial enumeration.

def dfs_iter(graph, src):
    stack = [src]
    visited = set([src])
    order = []
    while stack:
        u = stack.pop()
        order.append(u)
        # Push neighbors in reverse so the popped order matches recursive order
        for v in reversed(graph[u]):
            if v not in visited:
                visited.add(v)
                stack.append(v)
    return order

print(dfs_iter({'A': ['B', 'C'], 'B': ['D', 'E'], 'C': ['F'],
                'D': [], 'E': ['F'], 'F': []}, 'A'))
# ['A', 'B', 'D', 'E', 'F', 'C']

Sameness: both produce the same set of visited vertices in the same connected component. Both run in $O(V+E)$.

Differences:

• Neighbor order matters. Recursive DFS visits children in the order they appear in the adjacency list. Iterative DFS with naive push order visits them in reverse. Push in reverse to match.
• "Visited" timing. Mark visited on push (above) vs on pop. The pop variant lets the same vertex appear in the stack multiple times — fine for correctness but wastes memory and breaks the discover-time tracking. Mark on push for cleaner semantics.
• Stack overflow. Recursive DFS hits Python's default 1000-frame recursion limit on long paths. Iterative DFS uses heap memory and scales to the graph size. For graph-trace problems with chain-like structure (e.g., a million-vertex linked list as a graph), iterative is the only option.
• Finish timestamps. The recursive version naturally has a "return" moment to record finish time. The iterative version needs an explicit "finish" event on the stack (e.g., push a sentinel like ("FINISH", u)) to recover this — at which point the iterative code is no simpler than the recursive.

Practical recommendation: write DFS recursively unless you specifically need iterative for stack-overflow reasons. The recursive form is shorter, mirrors the math more directly, and integrates with the call stack's natural finish-event timing.