Topics › Graphs › Learning

DFS

Medium TUF ID 2831 A2ZSDE

Java source ↗ Edit this article ↗

Jump to code: Brute Better Optimal

Problem

You are given a graph as an adjacency list adj over vertices 0..V-1 and a start vertex, usually 0. Return the vertices in depth-first order: visit the start, then take its first neighbour and explore everything reachable from it before coming back to try the start’s second neighbour, and so on. Neighbours are tried in the order they appear in adj, and every vertex is listed once. Only vertices reachable from the start appear.

Constraints: 1 ≤ V, E ≤ 10^4. The graph may be directed or undirected; the algorithm is the same.

Example 1

edges (undirected): 0-1, 0-2, 0-3, 2-4
adj = [[1,2,3], [0], [0,4], [0], [2]]
answer = [0, 1, 2, 4, 3]      // after 2, DFS goes down to 4 before returning for 3

Example 2

edges (undirected): 0-1, 0-2, 1-3, 2-3, 3-4, 4-5
adj = [[1,2], [0,3], [0,3], [1,2,4], [3,5], [4]]
answer = [0, 1, 3, 2, 4, 5]   // 0 -> 1 -> 3 -> 2, back to 3 -> 4 -> 5

Compare with BFS on the same graphs, which gives 0 1 2 3 4 and 0 1 2 3 4 5. BFS spreads out layer by layer; DFS commits to one branch and only backtracks when that branch is exhausted.

Approach 1: Recursion

Intuition. The definition of DFS is recursive: “to explore u, mark it, then explore each unvisited neighbour of u in turn”. The call stack remembers where to come back to, and the visited array guarantees that each vertex is explored once, which also stops the search from running around a cycle forever. A vertex is recorded the moment it is first entered, which gives the preorder that problems ask for.

Algorithm.

1. Mark u visited and append it to the answer.
2. For each neighbour v of u in list order: if v is not visited, recurse into v.

static List<Integer> recursive(List<List<Integer>> adj, int start) {
    List<Integer> order = new ArrayList<>();
    dfs(adj, start, new boolean[adj.size()], order);
    return order;
}

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

Dry run on example 2:

Complexity. Time O(V + E): each vertex is entered once and each adjacency list is scanned once. Space O(V) for the visited array plus the recursion depth, which can reach V on a long path.

That depth is the practical weakness. The JVM’s default thread stack holds somewhere between ten thousand and a few tens of thousands of frames like these, so a path of 10^5 vertices can throw StackOverflowError. The tests run the recursive version on a 3000-vertex path, which is safe, and use only the iterative versions on a 200000-vertex path.

Approach 2: Explicit stack of vertices

Intuition. Replace the call stack with a Deque used as a stack. Pop a vertex; if it was already visited, skip it; otherwise record it and push its unvisited neighbours. Two details make the order match the recursive version exactly:

• Push the neighbours in reverse order, so the first neighbour ends up on top and is explored first.
• Mark a vertex visited when it is popped, not when it is pushed. A vertex can sit in the stack several times; only the first pop counts, and later copies are skipped.

The second point deserves a closer look, because the tempting alternative (mark when pushed, like BFS) gives a different order. See “Why not mark on push?” below.

Algorithm.

1. Push start.
2. While the stack is not empty: pop u. If visited, continue. Otherwise mark it, record it, and push every unvisited neighbour from the last to the first.

static List<Integer> iterativeStack(List<List<Integer>> adj, int start) {
    List<Integer> order = new ArrayList<>();
    boolean[] visited = new boolean[adj.size()];
    Deque<Integer> stack = new ArrayDeque<>();
    stack.push(start);
    while (!stack.isEmpty()) {
        int u = stack.pop();
        if (visited[u]) continue;                     // pushed more than once; already explored
        visited[u] = true;
        order.add(u);
        List<Integer> nbrs = adj.get(u);
        for (int i = nbrs.size() - 1; i >= 0; i--) {
            int v = nbrs.get(i);
            if (!visited[v]) stack.push(v);
        }
    }
    return order;
}

Complexity. Time O(V + E): every push corresponds to scanning one adjacency-list entry. Space O(E) in the worst case, because stale duplicates can accumulate in the stack, but no recursion at all.

Approach 3: Simulating the call stack exactly

Intuition. What does a recursive call actually remember? The vertex it is exploring and how far it has got through that vertex’s neighbour list. Store exactly that: a frame {vertex, nextIndex}. Look at the top frame; if its vertex has no neighbours left, pop it (“return”); otherwise take the next neighbour, advance the index, and if that neighbour is unvisited, visit it and push a new frame (“call”). This is a mechanical translation of approach 1, so it produces the same order, and since each vertex has at most one frame on the stack, the stack never exceeds V entries.

Algorithm.

1. Visit start and push the frame {start, 0}.
2. While the stack is not empty: let top be the top frame. If top.nextIndex equals the length of its neighbour list, pop it. Otherwise read neighbour v = adj[top.vertex][top.nextIndex] and increment the index; if v is unvisited, visit it and push {v, 0}.

static List<Integer> iterativeFrames(List<List<Integer>> adj, int start) {
    List<Integer> order = new ArrayList<>();
    boolean[] visited = new boolean[adj.size()];
    Deque<int[]> stack = new ArrayDeque<>();
    visited[start] = true;
    order.add(start);
    stack.push(new int[]{start, 0});
    while (!stack.isEmpty()) {
        int[] top = stack.peek();
        List<Integer> nbrs = adj.get(top[0]);
        if (top[1] == nbrs.size()) {                  // every neighbour tried: "return" from this call
            stack.pop();
            continue;
        }
        int v = nbrs.get(top[1]++);
        if (!visited[v]) {                            // "call" dfs(v)
            visited[v] = true;
            order.add(v);
            stack.push(new int[]{v, 0});
        }
    }
    return order;
}

nbrs.get(top[1]++) reads the current index and advances it in one step; because top is the very array stored in the deque, the update persists between iterations.

Complexity. Time O(V + E), space O(V). This is the version to reach for when you need DFS on huge inputs and also need post-order events, such as finishing times in topological sort or Kosaraju’s algorithm, because the moment a frame is popped is exactly the moment the recursive call would return.

Why not mark on push?

For BFS, marking on push is the right choice. For DFS it changes the result. Consider the directed graph 0->1, 0->2, 1->2, 1->4, 2->3. Recursive DFS goes 0, 1, 2, 3, backs up to 1, then visits 4: the order is 0 1 2 3 4. Here is the tempting variant:

static List<Integer> markOnPushWrong(List<List<Integer>> adj, int start) {
    List<Integer> order = new ArrayList<>();
    boolean[] visited = new boolean[adj.size()];
    Deque<Integer> stack = new ArrayDeque<>();
    visited[start] = true;
    stack.push(start);
    while (!stack.isEmpty()) {
        int u = stack.pop();
        order.add(u);
        List<Integer> nbrs = adj.get(u);
        for (int i = nbrs.size() - 1; i >= 0; i--) {
            int v = nbrs.get(i);
            if (!visited[v]) {
                visited[v] = true;
                stack.push(v);
            }
        }
    }
    return order;
}

Popping 0 marks and pushes both 1 and 2. When 1 is popped, its neighbour 2 is already marked, so only 4 is pushed, and 4 comes out next. The result is 0 1 4 2 3. Every vertex is still visited once, so it is a valid traversal, but it is not depth-first: vertex 2 was “claimed” by 0 even though DFS would reach it through 1 first. The tests check that approaches 1 to 3 give 0 1 2 3 4 on this graph and that this variant does not.

Edge cases and pitfalls

• Disconnected graphs. A DFS from one start reaches only its component. To cover all vertices, loop over every vertex and start a new DFS from each unvisited one, as in Connected Components.
• Recursion depth. Recursive DFS on a path of 10^5 vertices can overflow the stack in Java. Use approach 2 or 3, or run the recursion in a Thread created with a larger stack size.
• Reverse push order. Pushing neighbours in list order makes the iterative version explore the last neighbour first; the result is a valid DFS but not the expected one.
• Directed graphs. Only outgoing arrows are followed. From 0 in 0->1, 0->2, 1->3, 3->0, 2->3, 4->0 the order is 0 1 3 2, and vertex 4 is never reached.
• Single vertex. The answer is [start].

Related problems

• Traversal Techniques is BFS, the layer-by-layer counterpart.
• Number of provinces counts DFS starts on an adjacency matrix.
• Flood fill algorithm is DFS on the implicit graph of a grid.
• Detect a cycle in an undirected graph adds parent tracking to DFS.
• Topo Sort records vertices when their DFS call returns.