Depth-first search

Written Explanation

The idea: go deep, then back up

From the current node, DFS picks the first unvisited neighbor and moves there. From that node it again picks the first unvisited neighbor, and so on. When a node has no unvisited neighbors left, DFS returns to the previous node and tries its next neighbor. It stops when it has backed all the way to the start with nothing left to try.

void dfs(String node, Set<String> visited) {
    if (!visited.add(node)) return;
    for (String next : g.getOrDefault(node, List.of())) {
        dfs(next, visited);
    }
}

Reading it:

• visited.add(node) returns false if the node was already seen. Then we return at once: that is the visited check, and it is what stops cycles.
• Otherwise the node is new. We then call dfs on every neighbor, one after another. Each recursive call explores completely before the next neighbor is tried.

The "back up" step is automatic. When a call returns, control goes back to the caller's loop, which moves to its next neighbor. The call stack remembers the path from the start to the current node.

Why the visited set is still needed

The rule from BFS applies here. In a graph with a cycle, A calls B and B calls A, which calls B again, forever. In recursive DFS that failure shows up sooner than a never-ending loop: it ends with a StackOverflowError, as you saw in the recursion lessons. The visited set cuts the loop on the second visit.

DFS with an explicit stack

Recursion is not the only way. You can replace the call stack with your own Deque used as a stack (push and pop). This matters for very deep graphs, as we will see.

Deque<String> stack = new ArrayDeque<>();
stack.push(start);
while (!stack.isEmpty()) {
    String cur = stack.pop();
    if (!visited.add(cur)) continue;
    // process cur here
    List<String> ns = g.getOrDefault(cur, List.of());
    for (int i = ns.size() - 1; i >= 0; i--) stack.push(ns.get(i));
}

Two details. First, a node can be pushed several times before it is popped, so the visited check happens at pop time, not at push time. Second, the stack is last in, first out. To visit neighbors in the same order as the recursive version, push them in reverse so the first neighbor ends up on top. If you push them in normal order, the traversal is still a valid DFS, but it visits the last neighbor first, so the order differs.

Compare the structures: BFS uses a queue and finds the nearest nodes first. DFS uses a stack, which is either the call stack or your own, and finds the deepest nodes first.

Cost

DFS marks each node once and scans each adjacency list once, so its cost is O(V + E), the same as BFS. A standard reference gives the same bound for DFS. The difference is not speed but memory and order. BFS memory grows with the width of the graph (a whole ring in the queue). DFS memory grows with its depth (the path from the start). Recursive DFS on a graph that is one long chain needs one stack frame per node, which is the next point.

Depth limits

The JVM's call stack is finite. Recursive DFS on a very long chain, such as 100,000 nodes in a row, can end in StackOverflowError. The exact limit depends on the JVM settings and the size of each frame, so do not rely on a particular number. The iterative version uses heap memory for its stack and handles such graphs, as the third example shows.

DFS does not find the shortest path

DFS commits to the first neighbor, and it records a path to a node as "whatever way I happened to arrive". That route can wind through half the graph. A standard reference makes this point: in a tree, DFS paths are the only paths so they are shortest, but on a general graph this is not the case.

Choosing between BFS and DFS

When in doubt, ask whether you need the shortest route. If yes, BFS.