DEV Community

Dev Cookies
Dev Cookies

Posted on

πŸ“˜ Blog 3: DFS Pattern (Path Exploration, Connectivity, Components) 🌐

πŸ”Ή Why DFS Matters?

Depth-First Search (DFS) explores a graph/tree as far as possible along one branch before backtracking.
Think of a maze explorer: keep going forward until you hit a wall, then backtrack and try a different path.

DFS is used when:

  • You want to explore all possible paths (e.g., backtracking problems).
  • You need connectivity detection (components, cycles).
  • Graph is huge, and recursion helps break it naturally.

πŸ”Ή DFS Core Idea

  1. Start from a source node.
  2. Recursively (or using a stack) visit an unvisited neighbor.
  3. Backtrack when no unvisited neighbors remain.

πŸ”Ή DFS Template in Java

Recursive DFS

import java.util.*;

public class DFSExample {
    public static void dfs(int node, boolean[] visited, List<List<Integer>> graph) {
        visited[node] = true;
        System.out.print(node + " ");

        for (int neighbor : graph.get(node)) {
            if (!visited[neighbor]) {
                dfs(neighbor, visited, graph);
            }
        }
    }

    public static void main(String[] args) {
        int n = 5; 
        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i < n; i++) graph.add(new ArrayList<>());

        // Undirected edges
        graph.get(0).add(1); graph.get(1).add(0);
        graph.get(0).add(2); graph.get(2).add(0);
        graph.get(1).add(3); graph.get(3).add(1);
        graph.get(2).add(4); graph.get(4).add(2);

        boolean[] visited = new boolean[n];
        dfs(0, visited, graph); // Output: 0 1 3 2 4
    }
}
Enter fullscreen mode Exit fullscreen mode

Iterative DFS (using stack)

public void dfsIterative(int start, List<List<Integer>> graph) {
    boolean[] visited = new boolean[graph.size()];
    Stack<Integer> stack = new Stack<>();
    stack.push(start);

    while (!stack.isEmpty()) {
        int node = stack.pop();
        if (!visited[node]) {
            visited[node] = true;
            System.out.print(node + " ");

            for (int neighbor : graph.get(node)) {
                if (!visited[neighbor]) {
                    stack.push(neighbor);
                }
            }
        }
    }
}
Enter fullscreen mode Exit fullscreen mode

πŸ”Ή DFS Use Cases (Patterns)

1. Path Exploration

DFS is the go-to for exploring all possible paths.

πŸ‘‰ Example: Path from source to destination in DAG

public boolean hasPath(List<List<Integer>> graph, int src, int dest, boolean[] visited) {
    if (src == dest) return true;
    visited[src] = true;
    for (int neighbor : graph.get(src)) {
        if (!visited[neighbor] && hasPath(graph, neighbor, dest, visited)) {
            return true;
        }
    }
    return false;
}
Enter fullscreen mode Exit fullscreen mode

πŸ‘‰ Related Problems:

  • Word Search (LeetCode 79)
  • N-Queens
  • All Paths from Source to Target (LeetCode 797)

2. Connected Components

DFS helps find how many disconnected parts exist in a graph.

πŸ‘‰ Example: Count connected components in undirected graph

public int countComponents(int n, int[][] edges) {
    List<List<Integer>> graph = new ArrayList<>();
    for (int i = 0; i < n; i++) graph.add(new ArrayList<>());
    for (int[] e : edges) {
        graph.get(e[0]).add(e[1]);
        graph.get(e[1]).add(e[0]);
    }

    boolean[] visited = new boolean[n];
    int count = 0;

    for (int i = 0; i < n; i++) {
        if (!visited[i]) {
            dfs(i, visited, graph);
            count++;
        }
    }
    return count;
}
Enter fullscreen mode Exit fullscreen mode

πŸ‘‰ Related Problems:

  • Number of Islands (LeetCode 200)
  • Connected Components in Graph (LeetCode 323)

3. Cycle Detection

DFS helps detect cycles in both directed and undirected graphs.

πŸ‘‰ Cycle detection in undirected graph

public boolean hasCycleUndirected(int node, int parent, boolean[] visited, List<List<Integer>> graph) {
    visited[node] = true;
    for (int neighbor : graph.get(node)) {
        if (!visited[neighbor]) {
            if (hasCycleUndirected(neighbor, node, visited, graph)) return true;
        } else if (neighbor != parent) {
            return true;
        }
    }
    return false;
}
Enter fullscreen mode Exit fullscreen mode

πŸ‘‰ Cycle detection in directed graph (using recursion stack)

public boolean hasCycleDirected(int node, boolean[] visited, boolean[] recStack, List<List<Integer>> graph) {
    if (recStack[node]) return true;
    if (visited[node]) return false;

    visited[node] = true;
    recStack[node] = true;

    for (int neighbor : graph.get(node)) {
        if (hasCycleDirected(neighbor, visited, recStack, graph)) return true;
    }

    recStack[node] = false;
    return false;
}
Enter fullscreen mode Exit fullscreen mode

πŸ‘‰ Related Problems:

  • Course Schedule (LeetCode 207)
  • Detect Cycle in Graph

4. Topological Sorting (DFS-based)

DFS can be used to generate topological order in DAGs.

public void topoSortDFS(int node, boolean[] visited, Stack<Integer> stack, List<List<Integer>> graph) {
    visited[node] = true;
    for (int neighbor : graph.get(node)) {
        if (!visited[neighbor]) {
            topoSortDFS(neighbor, visited, stack, graph);
        }
    }
    stack.push(node);
}
Enter fullscreen mode Exit fullscreen mode

πŸ‘‰ Related Problems:

  • Course Schedule II (LeetCode 210)

5. Backtracking (DFS with undo step)

DFS naturally extends to backtracking problems.

πŸ‘‰ Example: Word Search (LeetCode 79)

public boolean exist(char[][] board, String word) {
    int m = board.length, n = board[0].length;
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (dfs(board, word, 0, i, j)) return true;
        }
    }
    return false;
}

private boolean dfs(char[][] board, String word, int idx, int i, int j) {
    if (idx == word.length()) return true;
    if (i<0 || j<0 || i>=board.length || j>=board[0].length || board[i][j] != word.charAt(idx)) 
        return false;

    char temp = board[i][j];
    board[i][j] = '#'; // mark visited

    boolean found = dfs(board, word, idx+1, i+1, j) || dfs(board, word, idx+1, i-1, j) ||
                    dfs(board, word, idx+1, i, j+1) || dfs(board, word, idx+1, i, j-1);

    board[i][j] = temp; // undo (backtrack)
    return found;
}
Enter fullscreen mode Exit fullscreen mode

πŸ”Ή DFS Interview Problem Map

  • Path Exploration: Word Search, N-Queens, All Paths.
  • Connectivity: Number of Islands, Connected Components.
  • Cycle Detection: Course Schedule, Detect Cycle in Graph.
  • Topological Sort: Course Schedule II.
  • Backtracking: Sudoku Solver, Word Search, Combinations/Permutations.

πŸ”Ή DFS Complexity

  • Time: O(V + E) (Vertices + Edges).
  • Space:

    • Recursive stack: O(V) in worst case.
    • Iterative DFS: O(V) for stack + visited.

βœ… Key Takeaway:
DFS is the Swiss Army knife for exploration problems:

  • Useful when you need to explore all paths, detect cycles, or analyze connectivity.
  • Natural fit for backtracking problems (try β†’ explore β†’ undo).

Top comments (0)