πΉ 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
- Start from a source node.
- Recursively (or using a stack) visit an unvisited neighbor.
- 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
}
}
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);
}
}
}
}
}
πΉ 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;
}
π 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;
}
π 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;
}
π 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;
}
π 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);
}
π 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;
}
πΉ 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.
- Recursive stack:
β
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)