Implement Depth-First Search

Given a directed graph with n vertices numbered 0 to n - 1, return the vertices in depth-first order:

• Start at vertex 0.
• Follow a vertex's neighbors in the order they appear in its adjacency list, going as deep as possible before backtracking.
• If some vertices haven't been reached, start again from the lowest-numbered unvisited vertex.

Example

graph LR
    0 --> 1
    0 --> 2
    1 --> 3
    2 --> 3
    3 --> 4
    5 --> 4

Adjacency list:  0: [1, 2]   1: [3]   2: [3]   3: [4]   4: []   5: [4]
Output:          [0, 1, 3, 4, 2, 5]

From 0, DFS goes to 1, then 3, then 4. Vertex 4 has no neighbors, so it backtracks to 3, then 1 (nothing new), then 0, whose next neighbor 2 hasn't been visited. Vertex 5 is unreachable from 0, so it starts a new search.

Compare with BFS on the same graph: [0, 1, 2, 3, 4, 5]. BFS visits vertices closest to the start first. DFS follows one path to its end first.

Recursive DFS

Visiting a vertex means: mark it, record it, then visit each unvisited neighbor recursively. The call stack remembers where to continue when a branch is finished.

Walkthrough (indentation shows recursion depth):

visit 0
  visit 1
    visit 3
      visit 4        (no neighbors, return)
    (3 done)
  (1 done)
  visit 2            (neighbor 3 already visited)
(0 done)
visit 5              (neighbor 4 already visited)

import java.util.ArrayList;
import java.util.List;

public class Main {
    static void visit(List<List<Integer>> adj, int v, boolean[] visited, List<Integer> order) {
        visited[v] = true;
        order.add(v);
        for (int w : adj.get(v)) {
            if (!visited[w]) {
                visit(adj, w, visited, order);
            }
        }
    }

    static List<Integer> dfs(List<List<Integer>> adj) {
        boolean[] visited = new boolean[adj.size()];
        List<Integer> order = new ArrayList<>();
        for (int start = 0; start < adj.size(); start++) {
            if (!visited[start]) {
                visit(adj, start, visited, order);
            }
        }
        return order;
    }

    public static void main(String[] args) {
        List<List<Integer>> adj = List.of(
            List.of(1, 2), List.of(3), List.of(3), List.of(4), List.of(), List.of(4));
        System.out.println(dfs(adj));
    }
}

[0, 1, 3, 4, 2, 5]

Time: O(V + E): each vertex is visited once, and each edge is checked once. Space: O(V) for visited and the recursion. The recursion can be V calls deep. Each call uses space on the thread's stack, whose size is limited. On a long chain of vertices (for example, 100,000 vertices in a line) the recursive version can throw StackOverflowError.

Iterative DFS with an explicit stack

Replace the call stack with an ArrayDeque used as a stack (push and pop work on the front). List.of(...) builds an immutable list. Two details make it visit vertices in the same order as the recursive version:

1. Push neighbors in reverse order, so the first neighbor is on top and gets popped first.
2. Mark a vertex visited when it's popped, not when it's pushed, and skip it if it's already visited. A vertex can be pushed several times (once by each neighbor that sees it before it's processed), but it's processed only once.

Walkthrough from vertex 0 (the stack's top is on the right):

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

public class Main {
    static List<Integer> dfs(List<List<Integer>> adj) {
        boolean[] visited = new boolean[adj.size()];
        List<Integer> order = new ArrayList<>();
        Deque<Integer> stack = new ArrayDeque<>();
        for (int start = 0; start < adj.size(); start++) {
            stack.push(start);
            while (!stack.isEmpty()) {
                int v = stack.pop();
                if (visited[v]) {
                    continue;
                }
                visited[v] = true;
                order.add(v);
                List<Integer> neighbors = adj.get(v);
                for (int i = neighbors.size() - 1; i >= 0; i--) {
                    int w = neighbors.get(i);
                    if (!visited[w]) {
                        stack.push(w);
                    }
                }
            }
        }
        return order;
    }

    public static void main(String[] args) {
        List<List<Integer>> adj = List.of(
            List.of(1, 2), List.of(3), List.of(3), List.of(4), List.of(), List.of(4));
        System.out.println(dfs(adj));

        // A chain of 100,000 vertices: 0 -> 1 -> 2 -> ... -> 99,999
        int n = 100_000;
        List<List<Integer>> chain = new ArrayList<>();
        for (int v = 0; v < n; v++) {
            chain.add(v + 1 < n ? List.of(v + 1) : List.of());
        }
        System.out.println(dfs(chain).size());
    }
}

[0, 1, 3, 4, 2, 5]
100000

Time: O(V + E). Space: O(V + E) in the worst case, since a vertex can be on the stack once per incoming edge. There's no recursion, so the 100,000-vertex chain is fine.

Both versions visit vertices in the same order and have the same time complexity. The recursive one is shorter. The iterative one does not depend on the thread stack size, so it is safe on deep graphs.

Where DFS is used

• Checking whether one vertex can reach another.
• Finding cycles in a directed graph (with three vertex states).
• Topological sorting: record each vertex after all its descendants are finished, then reverse the list.
• Counting connected components: count how many times the outer for start loop starts a new search.