This content originally appeared on DEV Community and was authored by Dev Cookies
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).
This content originally appeared on DEV Community and was authored by Dev Cookies