Graph DFS
Overview
Depth-First Search (DFS) on a Graph is conceptually identical to Tree DFS: you pick a path and plunge as deeply as possible until you hit a dead end, then backtrack and try the next path.
However, there is one massive difference. Because graphs can have Cycles (Node A connects to Node B, which connects to Node C, which connects back to Node A), a naive recursive DFS will run in circles forever until the JVM crashes with a StackOverflowError.
To prevent this fatal flaw, Graph DFS introduces a mandatory Visited Set to track which nodes have already been processed. Every time DFS visits a node, it adds it to the set. Before exploring a neighbor, it checks the set. If the neighbor is already in the set, it instantly skips it and backtracks.
Syntax
import java.util.*;
public class GraphDFS {
Map<Integer, List<Integer>> adjList = new HashMap<>();
// Entry point for DFS
public void traverse(int startNode) {
// Crucial: The Visited Set prevents infinite cyclic loops
Set<Integer> visited = new HashSet<>();
dfs(startNode, visited);
}
private void dfs(int current, Set<Integer> visited) {
// Mark as visited immediately upon entry!
visited.add(current);
// Process current node
System.out.println("Visited: " + current);
// Iterate through all connected neighbors
for (int neighbor : adjList.getOrDefault(current, new ArrayList<>())) {
// Only recurse if the neighbor has NEVER been visited
if (!visited.contains(neighbor)) {
dfs(neighbor, visited);
}
}
}
}Common Pitfalls
- Forgetting the visited set. This is guaranteed to cause infinite loops and crashes in cyclic graphs.
- Marking nodes visited too late. If you wait until after the recursive call returns to mark a node visited, other branches might explore it in the meantime.
- Global visited sets in disconnected graphs. If a graph is broken into multiple disconnected 'islands', running DFS from one node won't visit the whole graph. You must loop through all vertices and call DFS on any that are not yet in the visited set.
Interview Questions
Graph DFS strictly requires cycle detection using a visited structure (Set or boolean array). Tree DFS does not, because valid trees mathematically cannot contain cycles.
Iterate through all nodes. If a node is unvisited, increment an 'island counter', and run DFS from that node. The DFS will mark all connected nodes as visited. The final counter value is the number of islands.
Real-World Example
Flood Fill Algorithms in Image Editing. When you use the 'Paint Bucket' tool in Photoshop to fill an area, the software runs a Graph DFS. Every pixel is a node, connected to adjacent pixels of the same color. DFS recursively paints all connected matching pixels until it hits boundaries.
public class PaintBucket {
// 2D Graph DFS (Flood Fill)
public void floodFill(int[][] image, int r, int c, int newColor, int oldColor) {
// Bounds checking and Visited checking (is it already the new color?)
if (r < 0 || r >= image.length || c < 0 || c >= image[0].length
|| image[r][c] != oldColor || image[r][c] == newColor) {
return;
}
// Mark visited (change the color)
image[r][c] = newColor;
// Explore all 4 directions deeply
floodFill(image, r + 1, c, newColor, oldColor); // Down
floodFill(image, r - 1, c, newColor, oldColor); // Up
floodFill(image, r, c + 1, newColor, oldColor); // Right
floodFill(image, r, c - 1, newColor, oldColor); // Left
}
}Check Your Knowledge
Test your understanding of Graph DFS with these quick questions.