Java depth-first search: cycles and explicit work stacks

Java 8+. Use a JDK that supports this release.

Reachability is the promised result

A dependency graph asks which modules can be reached from a starting module. The sample counts them. It does not produce a topological order or prove the graph acyclic.

Mark a vertex before pushing it so pending work contains at most one entry per discovered vertex. The resulting visit order can differ from a recursive implementation because neighbours are scheduled together; reachability is unchanged.

Directed cycles are allowed. A simple visited flag skips a previously discovered vertex, but cycle detection needs more information when it must distinguish an edge into the active path from an edge into a completed branch.

Avoid recursion for unbounded depth

A long chain can exhaust a Java thread’s call stack in a recursive traversal. An explicit deque moves pending state to ordinary heap storage. It still needs a memory budget; it is not an unlimited traversal.

The graph is assumed structurally stable during the call. Mutating adjacency rows while traversing changes the input contract and can make results timing-dependent.

Working program

import java.util.ArrayDeque;
import java.util.Deque;

public class DependencyReachability {
    static int reachable(int[][] dependencies, int source) {
        if (source < 0 || source >= dependencies.length) throw new IllegalArgumentException("Invalid source");
        boolean[] discovered = new boolean[dependencies.length];
        Deque<Integer> pending = new ArrayDeque<>();
        pending.push(source); discovered[source] = true;
        int count = 0;
        while (!pending.isEmpty()) {
            int module = pending.pop(); count++;
            for (int next : dependencies[module]) {
                if (next < 0 || next >= dependencies.length) throw new IllegalArgumentException("Invalid edge");
                if (!discovered[next]) { discovered[next] = true; pending.push(next); }
            }
        }
        return count;
    }
    public static void main(String[] args) {
        int[][] dependencies = {{1}, {2}, {0, 3}, {}, {}};
        System.out.println(reachable(dependencies, 0));
    }
}

Output

4

Cost and design choices

Visited-state initialization and adjacency scanning require O(V + E) worst-case work and O(V) extra storage. For a sparse reachable component, edge scanning is limited to that component, while the boolean array still covers all vertices.

Counting reachability does not retain a full traversal result. Adding a result list or predecessor structure adds its own memory cost and output semantics.

Common Mistakes

• Do not omit visited state on a cyclic graph.
• Do not describe this count as a topological ordering.
• Do not assume its work-stack order is identical to recursive DFS.

Connect the contracts

An explicit work stack changes the stack depth failure boundary.

One traversal is not enough to establish mutual reachability; study strong components.

Extend the tested workflow

Continue with Java graph bridges: track edge identity when parallel edges exist.