DFS

How DFS Works

DFS explores as far as possible along each branch before backtracking. It uses a stack (LIFO) or recursion (call stack).

Graph:        0
             / \
            1   2
           / \\   \
          3   4   5

DFS Order (starting at 0): 0 → 1 → 3 → 4 → 2 → 5
(Goes deep first, then backtracks)

Recursive DFS

import java.util.*;

public class DFS {
    
    // Simple recursive DFS
    public void dfsRecursive(Map<Integer, List<Integer>> graph, int node, Set<Integer> visited) {
        visited.add(node);
        System.out.print(node + " ");
        
        for (int neighbor : graph.get(node)) {
            if (!visited.contains(neighbor)) {
                dfsRecursive(graph, neighbor, visited);
            }
        }
    }
    
    // DFS that returns a list
    public List<Integer> dfs(Map<Integer, List<Integer>> graph, int start) {
        List<Integer> result = new ArrayList<>();
        Set<Integer> visited = new HashSet<>();
        dfsHelper(graph, start, visited, result);
        return result;
    }
    
    private void dfsHelper(Map<Integer, List<Integer>> graph, int node, 
                          Set<Integer> visited, List<Integer> result) {
        visited.add(node);
        result.add(node);
        
        for (int neighbor : graph.get(node)) {
            if (!visited.contains(neighbor)) {
                dfsHelper(graph, neighbor, visited, result);
            }
        }
    }
}

Iterative DFS (Using Stack)

public List<Integer> dfsIterative(Map<Integer, List<Integer>> graph, int start) {
    List<Integer> result = new ArrayList<>();
    Set<Integer> visited = new HashSet<>();
    Stack<Integer> stack = new Stack<>();
    
    stack.push(start);
    
    while (!stack.isEmpty()) {
        int node = stack.pop();
        
        if (visited.contains(node)) continue;
        visited.add(node);
        result.add(node);
        
        // Push neighbors in reverse order for consistent order
        List<Integer> neighbors = graph.get(node);
        for (int i = neighbors.size() - 1; i >= 0; i--) {
            if (!visited.contains(neighbors.get(i))) {
                stack.push(neighbors.get(i));
            }
        }
    }
    
    return result;
}

DFS Template for Interview Problems

// Complete DFS template with path tracking
public boolean dfsPath(Map<Integer, List<Integer>> graph, int start, int target) {
    Set<Integer> visited = new HashSet<>();
    return dfsHelper(graph, start, target, visited);
}

private boolean dfsHelper(Map<Integer, List<Integer>> graph, int current, 
                         int target, Set<Integer> visited) {
    if (current == target) return true;
    visited.add(current);
    
    for (int neighbor : graph.get(current)) {
        if (!visited.contains(neighbor)) {
            if (dfsHelper(graph, neighbor, target, visited)) {
                return true;
            }
        }
    }
    
    return false;
}

Complexity Analysis

When to Use DFS

• Cycle Detection: Detecting cycles in directed/undirected graphs
• Connected Components: Counting/finding components
• Topological Sort: Ordering with dependencies
• Path Finding: Checking if path exists
• Backtracking: Exploring all possibilities
• Memoization: DFS + memoization (top-down dynamic programming)

Cycle Detection with DFS

Undirected Graph Cycle Detection

public boolean hasCycleUndirected(Map<Integer, List<Integer>> graph, int n) {
    boolean[] visited = new boolean[n];
    
    for (int i = 0; i < n; i++) {
        if (!visited[i]) {
            if (dfsCycleUndirected(graph, i, -1, visited)) {
                return true;
            }
        }
    }
    return false;
}

private boolean dfsCycleUndirected(Map<Integer, List<Integer>> graph, 
                                  int node, int parent, boolean[] visited) {
    visited[node] = true;
    
    for (int neighbor : graph.get(node)) {
        if (!visited[neighbor]) {
            if (dfsCycleUndirected(graph, neighbor, node, visited)) {
                return true;
            }
        } else if (neighbor != parent) {
            return true; // Found cycle
        }
    }
    
    return false;
}

Directed Graph Cycle Detection (3-Color Method)

public boolean hasCycleDirected(Map<Integer, List<Integer>> graph, int n) {
    int[] color = new int[n]; // 0: unvisited, 1: visiting, 2: visited
    
    for (int i = 0; i < n; i++) {
        if (color[i] == 0) {
            if (dfsCycleDirected(graph, i, color)) {
                return true;
            }
        }
    }
    return false;
}

private boolean dfsCycleDirected(Map<Integer, List<Integer>> graph, 
                                int node, int[] color) {
    color[node] = 1; // Mark as visiting
    
    for (int neighbor : graph.get(node)) {
        if (color[neighbor] == 1) {
            return true; // Back edge found - cycle!
        }
        if (color[neighbor] == 0) {
            if (dfsCycleDirected(graph, neighbor, color)) {
                return true;
            }
        }
    }
    
    color[node] = 2; // Mark as visited
    return false;
}

Number of Connected Components

public int countComponents(Map<Integer, List<Integer>> graph, int n) {
    boolean[] visited = new boolean[n];
    int components = 0;
    
    for (int i = 0; i < n; i++) {
        if (!visited[i]) {
            components++;
            dfsMarkComponent(graph, i, visited);
        }
    }
    
    return components;
}

private void dfsMarkComponent(Map<Integer, List<Integer>> graph, 
                             int node, boolean[] visited) {
    visited[node] = true;
    for (int neighbor : graph.get(node)) {
        if (!visited[neighbor]) {
            dfsMarkComponent(graph, neighbor, visited);
        }
    }
}

DFS on Grid (Flood Fill)

// Flood fill / Island counting
public void dfsGrid(int[][] grid, int r, int c, boolean[][] visited) {
    int rows = grid.length, cols = grid[0].length;
    
    if (r < 0 || r >= rows || c < 0 || c >= cols 
        || visited[r][c] || grid[r][c] == 0) {
        return;
    }
    
    visited[r][c] = true;
    
    int[][] dirs = {{-1,0}, {1,0}, {0,-1}, {0,1}};
    for (int[] dir : dirs) {
        dfsGrid(grid, r + dir[0], c + dir[1], visited);
    }
}

// Count islands
public int numIslands(char[][] grid) {
    int count = 0;
    boolean[][] visited = new boolean[grid.length][grid[0].length];
    
    for (int r = 0; r < grid.length; r++) {
        for (int c = 0; c < grid[0].length; c++) {
            if (grid[r][c] == '1' && !visited[r][c]) {
                count++;
                dfsGrid(grid, r, c, visited);
            }
        }
    }
    
    return count;
}

DFS with Backtracking

// All paths from source to target
public List<List<Integer>> allPaths(Map<Integer, List<Integer>> graph, 
                                   int start, int target) {
    List<List<Integer>> result = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    path.add(start);
    dfsAllPaths(graph, start, target, path, result);
    return result;
}

private void dfsAllPaths(Map<Integer, List<Integer>> graph, int current, 
                        int target, List<Integer> path, 
                        List<List<Integer>> result) {
    if (current == target) {
        result.add(new ArrayList<>(path));
        return;
    }
    
    for (int neighbor : graph.get(current)) {
        path.add(neighbor);
        dfsAllPaths(graph, neighbor, target, path, result);
        path.remove(path.size() - 1); // Backtrack
    }
}

Common DFS Problems