Graph DFS

Overview

Depth-First Search on a Graph dives deep down a single path until it hits a dead end, then backtracks. Just like Tree DFS, it is elegantly written using Recursion. The critical difference is that because graphs contain cycles (A connects to B, B connects to A), you absolutely MUST keep track of which nodes you have already visited to prevent infinite loops.

Syntax

The `visited` set ensures we never process the same node twice, breaking any infinite cycles.

Graph DFS with a Visited Set

java

public void dfs(Map<Integer, List<Integer>> graph, int current, Set<Integer> visited) {
    // If we've already been here, stop to prevent infinite loops!
    if (visited.contains(current)) return;
    
    // Mark as visited and process
    visited.add(current);
    System.out.println("Visited: " + current);
    
    // Recursively visit all neighbors
    for (int neighbor : graph.getOrDefault(current, new ArrayList<>())) {
        dfs(graph, neighbor, visited);
    }
}

Common Pitfalls

Forgetting the `visited.contains(current)` check at the top of the function. This is a guaranteed Stack Overflow Error.

Interview Tips

DFS is best for exploring all possible paths, topological sorting, and solving mazes/puzzles.

Real-World Example

Solving a Maze. You walk down a corridor until you hit a wall, then you walk back and try the other corridor.

example

java

// Maze solving usually uses DFS with Backtracking logic.

Take Java Quiz