Depth-First Search

Depth-first search follows one path as far as it goes, then backs up and tries the next. It is the same algorithm as BFS with one substitution: a stack instead of a queue.

The recursive form

    private void depthFirstRecursive(String current, Set<String> visited, List<String> order) {
        if (!visited.add(current)) {
            return;
        }
        order.add(current);
        for (String next : neighbours(current)) {
            depthFirstRecursive(next, visited, order);
        }
    }

Five lines. There is no explicit stack because the call stack is the stack — each frame remembers where to resume after the recursion returns, which is exactly the bookkeeping an explicit stack would do.

visited.add returning false for an already-visited vertex makes the guard and the marking one line, and it is what stops a cycle recursing forever.

The iterative form

        Set<String> visited = new HashSet<>();
        Deque<String> stack = new ArrayDeque<>();
        stack.push(start);

        while (!stack.isEmpty()) {
            String current = stack.pop();
            // Checked on POP here, not on push: a vertex can be pushed by several neighbours
            // before it is ever popped, so the pop is the only place it is certainly first.
            if (!visited.add(current)) {
                continue;
            }
            order.add(current);
            List<String> next = new ArrayList<>(neighbours(current));
            // Reversed so the first neighbour is explored first, matching the recursive version.
            for (int i = next.size() - 1; i >= 0; i--) {
                if (!visited.contains(next.get(i))) {
                    stack.push(next.get(i));
                }
            }
        }

Put the two side by side and the point of the chapter is visible: this is the BFS loop with queue.remove() replaced by stack.pop(). The traversal strategy is the container.

⚠️ Two differences from BFS that are easy to miss

1. Mark visited on pop, not on push. This is the opposite of BFS, and for a concrete reason. A vertex can be pushed by several neighbours before it is ever popped, so being on the stack does not mean it has been processed — the pop is the only moment you can be sure you are seeing it first. Marking on push would skip vertices that were pushed but not yet reached.

The consequence is that duplicates can sit on the stack, which is why the continue guard is needed. That is the price of the stack ordering, and it is why the recursive version — which cannot push duplicates — is usually cleaner.

2. Push neighbours in reverse. A stack reverses whatever you put into it, so pushing neighbours in order means popping them backwards. Iterating in reverse cancels that out and makes the iterative traversal match the recursive one:

        Check.eq(g.depthFirst("a").toString(), "[a, b, d, e, c]", "DFS follows one path down");
        Check.eq(g.depthFirstRecursive("a").toString(), "[a, b, d, e, c]", "recursive DFS agrees");

Without the reversal both are valid depth-first traversals — they just visit siblings in opposite orders, which makes the two implementations disagree and the tests non-portable.

Recursive or iterative?

Prefer the recursive form for its clarity, and switch to the iterative one when depth could exceed the stack. The threshold is real: a graph of a million vertices in a line will StackOverflowError the recursive version, while the iterative one is fine because ArrayDeque grows on the heap.

The "post-order work" row is why DFS is so much more useful than it first looks. Because the recursion returns, you get a natural place to run code after a vertex's whole subtree is done — which is precisely what topological sort and cycle detection need.

Complexity

O(V + E) time, identical to BFS. O(V) space, but for a different reason: BFS holds a whole level, DFS holds one path. On a wide, shallow graph DFS uses far less memory; on a deep, narrow one it uses more.

What DFS is genuinely for

BFS owns shortest paths. DFS owns everything that depends on finishing a subtree:

• Cycle detection. In a directed graph, a cycle is an edge back to a vertex still on the current path — the "grey" vertex in the classic three-colour marking. In an undirected graph it is an edge to a visited vertex that is not your parent.
• Topological sort. Run DFS and prepend each vertex as it finishes. The result is a valid build order — and if the graph has a cycle there is no such order, which the same traversal detects.
• Connected components. DFS from each unvisited vertex; each run is one component.
• Backtracking. Sudoku, N-queens, maze solving, permutation generation. Try a choice, recurse, undo it — that is DFS over a tree of possibilities that is never built in memory.
• Strongly connected components — Tarjan's and Kosaraju's algorithms are both DFS with extra bookkeeping.

Notice what those have in common: none is about distance. The moment a problem asks "how far" or "how few steps", it is a BFS problem.

⚠️ DFS does not find shortest paths

It finds a path, which is often much longer than the best one, because it commits to the first direction it tries and only backtracks when stuck. If you need the shortest route, use BFS for unweighted graphs and Dijkstra for weighted ones.

What to remember

• A stack — explicit, or the call stack via recursion.
• Mark visited on pop, the opposite of BFS, and guard against duplicates.
• Push neighbours in reverse to match the recursive order.
• O(V + E) time; memory scales with depth, not width.
• Recursive is clearer; iterative survives deep graphs.
• Cycles, topological sort, components and backtracking — never shortest paths.