8.3 Depth-First Search | Code Scholars Tutoring

How it works

DFS uses a stack, explicitly or through recursion, and goes deep before backtracking. It underpins cycle detection and topological ordering.

Detect a cycle in a directed graph by finding an edge back to a vertex still on the recursion stack.

Common error

Calling any edge to a visited vertex a cycle. An edge to a finished vertex is legal in an acyclic graph.

Worked example

Java snippets run inside a main method. Add import java.util.*; when collection types are used.

Java

Map<String,List<String>> graph = Map.of(
    "A", List.of("B","C"), "B", List.of("A","D"),
    "C", List.of("A","D"), "D", List.of("B","C"));
class Walker {
    Set<String> seen = new HashSet<String>();
    void visit(String node) {
        if (!seen.add(node)) return;
        System.out.print(node + " ");
        for (String next : graph.get(node)) visit(next);
    }
}
new Walker().visit("A");

Output

A B D C

Depth-first search follows one branch before returning to remaining alternatives. The visited set prevents repeated exploration around a cycle. Exact visit order depends on the neighbor order and implementation.

Edges are A-B, A-C, B-D, and C-D. — Edges A-B, A-C, B-D, and C-D; visit order depends on traversal strategy and neighbor order.

Exercises

8.3.1 · Explain

Give recursive DFS visit order from A using alphabetical neighbor order.

Show solution

A, B, D, C. From D, C is the next unvisited neighbor before recursion returns to A.

8.3.2 · Explain

Does DFS necessarily find the minimum-edge path to a target?