182. DFS Reachability

Why this mechanism works

Reachability needs to explore each discovered vertex only once. Mark a vertex when scheduling it on the DFS stack, so several incoming edges cannot create duplicate pending work. A stack determines exploration order but does not imply a shortest route.

State and boundaries

seen contains exactly the discovered vertices, each reachable from start. stack contains discovered vertices awaiting processing.

Protocol

1. Mark and push start.
2. Pop a vertex and test for target.
3. Mark and push each unseen neighbor.
4. Return false if the stack empties.

Visualization

0 -> 1 -> 2
^    |    |
|____|    v
          3
seen prevents the 1->0 cycle from rescheduling 0

Python implementation

def dfs_reachable(adj, start, target):
    stack, seen = [start], {start}
    while stack:
        u = stack.pop()
        if u == target:
            return True
        for v in adj[u]:
            if v not in seen:
                seen.add(v)
                stack.append(v)
    return False

Worked execution

Recorded state changes after statements; L numbers refer to the solution file. Long traces are explicitly condensed.

L2 dfs_reachable: stack, seen = [start], {start}
adj=[[1], [0, 2], [3], []]; start=0; target=3; stack=[0]; seen={0}

L4 dfs_reachable: u = stack.pop()
adj=[[1], [0, 2], [3], []]; start=0; target=3; stack=[]; seen={0}; u=0

L7 dfs_reachable: for v in adj[u]:
adj=[[1], [0, 2], [3], []]; start=0; target=3; stack=[]; seen={0}; u=0; v=1

L9 dfs_reachable: seen.add(v)
adj=[[1], [0, 2], [3], []]; start=0; target=3; stack=[]; seen={0, 1}; u=0; v=1

L10 dfs_reachable: stack.append(v)
adj=[[1], [0, 2], [3], []]; start=0; target=3; stack=[1]; seen={0, 1}; u=0; v=1

L4 dfs_reachable: u = stack.pop()
adj=[[1], [0, 2], [3], []]; start=0; target=3; stack=[]; seen={0, 1}; u=1; v=1

L7 dfs_reachable: for v in adj[u]:
adj=[[1], [0, 2], [3], []]; start=0; target=3; stack=[]; seen={0, 1}; u=1; v=0

L7 dfs_reachable: for v in adj[u]:
adj=[[1], [0, 2], [3], []]; start=0; target=3; stack=[]; seen={0, 1}; u=1; v=2

... 3 intermediate state changes omitted ...

L7 dfs_reachable: for v in adj[u]:
adj=[[1], [0, 2], [3], []]; start=0; target=3; stack=[]; seen={0, 1, 2}; u=2; v=3

L9 dfs_reachable: seen.add(v)
adj=[[1], [0, 2], [3], []]; start=0; target=3; stack=[]; seen={0, 1, 2, 3}; u=2; v=3

L10 dfs_reachable: stack.append(v)
adj=[[1], [0, 2], [3], []]; start=0; target=3; stack=[3]; seen={0, 1, 2, 3}; u=2; v=3

L4 dfs_reachable: u = stack.pop()
adj=[[1], [0, 2], [3], []]; start=0; target=3; stack=[]; seen={0, 1, 2, 3}; u=3; v=3

L2 dfs_reachable: stack, seen = [start], {start}
adj=[[1], [], []]; start=0; target=2; stack=[0]; seen={0}

L4 dfs_reachable: u = stack.pop()
adj=[[1], [], []]; start=0; target=2; stack=[]; seen={0}; u=0

L7 dfs_reachable: for v in adj[u]:
adj=[[1], [], []]; start=0; target=2; stack=[]; seen={0}; u=0; v=1

L9 dfs_reachable: seen.add(v)
adj=[[1], [], []]; start=0; target=2; stack=[]; seen={0, 1}; u=0; v=1

L10 dfs_reachable: stack.append(v)
adj=[[1], [], []]; start=0; target=2; stack=[1]; seen={0, 1}; u=0; v=1

L4 dfs_reachable: u = stack.pop()
adj=[[1], [], []]; start=0; target=2; stack=[]; seen={0, 1}; u=1; v=1

Why the solution is correct

The start is reachable, and every newly scheduled neighbor extends a known path. Thus a returned target is reachable. If the search exhausts, every edge from every discovered vertex has been explored, so no reachable vertex remains undiscovered. Each vertex is scheduled at most once.

Time and space

O(V+E) worst-case time and O(V) auxiliary space over the reachable portion of the graph.

Common mistakes

Marking only after pop permits duplicate scheduling. A visited value must identify the vertex, not a possibly repeated display label.

Reasoning card

Transfer exercise

Store a parent when discovering each vertex and reconstruct one path when the target is reached.