The DFS Template

1.Recursive DFS

dfs(u): mark u visited; for each neighbour v, if not visited, dfs(v). Each node is visited once and each edge examined once per direction: O(V + E) time, O(V) space for the visited array and up to O(V) recursion depth.

Java's default thread stack handles depths of roughly 10⁴ frames comfortably; for a 10⁵-node path graph, use an explicit stack (or run inside a Thread with a bigger stack size).

import java.util.*;

public class Main {
    static List<List<Integer>> adj = new ArrayList<>();
    static boolean[] seen;
    static List<Integer> order = new ArrayList<>();

    static void dfs(int u) {
        seen[u] = true;
        order.add(u);
        for (int v : adj.get(u)) if (!seen[v]) dfs(v);
    }

    public static void main(String[] args) {
        int n = 5;
        int[][] edges = {{0, 1}, {0, 2}, {1, 3}, {2, 3}, {3, 4}};
        for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
        for (int[] e : edges) { adj.get(e[0]).add(e[1]); adj.get(e[1]).add(e[0]); }
        seen = new boolean[n];
        dfs(0);
        System.out.println("visit order: " + order);
    }
}

visit order: [0, 1, 3, 2, 4]

2.DFS vs BFS

In the run above DFS goes 0 → 1 → 3 → 2 before reaching 4, while BFS would visit 0, 1, 2, 3, 4 by distance. Both find everything reachable; only BFS finds fewest-step paths. Choose DFS for components, flood fill, path enumeration, cycle detection and topological order; choose BFS for distances.