Depth-First Search (DFS) & Applications

Introduction

In our last post, we explored Breadth-First Search (BFS), which expands like finding friends-of-friends. It goes wide before it goes deep.

Depth-First Search (DFS) does the exact opposite. It picks a path and follows it as far as possible until it hits a dead end. When it can’t go any further, it backtracks to the last intersection and tries a different path.

Think of exploring a physical maze. You don’t take one step down every corridor simultaneously (BFS). You walk down one corridor until you hit a wall, then turn around and try the next branch.

How DFS Works

While BFS uses a Queue (First In, First Out) to ensure we visit all neighbours first, DFS uses a Stack (Last In, First Out). The most recent node we discovered is the first one we explore further.

Because the Call Stack in our programming language is a Stack, DFS is almost always implemented recursively, making the code incredibly short and elegant.

The Algorithm

1. Start at a node.
2. Mark it as visited (crucial to avoid infinite loops in cyclic graphs).
3. Look at its neighbours.
4. For every unvisited neighbour, recursively call DFS on it.

The DFS Implementation (Recursive)

Let’s use the Adjacency List graph representation we built in the previous post.

import java.util.*;

public class GraphDFS {
    Map<String, List<String>> adjList = new HashMap<>();

    // The wrapper method that users call
    public void dfs(String startNode) {
        Set<String> visited = new HashSet<>();
        dfsHelper(startNode, visited);
    }

    // The recursive helper method
    private void dfsHelper(String current, Set<String> visited) {
        // 1. Mark current as visited
        visited.add(current);
        System.out.print(current + " "); // Process the node

        // 2. Visit all unvisited neighbours
        if (adjList.containsKey(current)) {
            for (String neighbour : adjList.get(current)) {
                if (!visited.contains(neighbour)) {
                    // Recursive call dives DEEP into this neighbour
                    dfsHelper(neighbour, visited);
                }
            }
        }
    }
}

The Walkthrough

Let’s trace DFS on this graph, starting at A: A -> [B, C], B -> [D, E], C -> [F], D -> [], E -> [F], F -> []

1. Start A. Mark visited. Print A.
2. Look at neighbours of A: [B, C].
3. Pick B. Unvisited. Recurse into B.
   • Mark B visited. Print B.
   • Look at neighbours of B: [D, E].
   • Pick D. Unvisited. Recurse into D.
     • Mark D visited. Print D.
     • Neighbours of D: []. Dead end. Backtrack to B.
   • Pick E. Unvisited. Recurse into E.
     • Mark E visited. Print E.
     • Neighbours of E: [F]. Recurse into F.
       • Mark F visited. Print F.
       • Neighbours of F: []. Backtrack to E.
     • Backtrack to B.
   • Backtrack to A.
4. Pick C. Unvisited. Recurse into C.
   • Mark C visited. Print C.
   • Neighbours of C: [F]. Wait, F is ALREADY VISITED. Skip.
   • Backtrack to A.
5. Finished.

DFS Output Order: A, B, D, E, F, C

(Compare this to BFS exactly matching layer-by-layer: A, B, C, D, E, F)

Iterative DFS (Using a Stack)

Sometimes, recursion goes too deep and causes a StackOverflowError. We can simulate the Call Stack by using an actual Stack object.

public void dfsIterative(String startNode) {
    Set<String> visited = new HashSet<>();
    Stack<String> stack = new Stack<>(); // Or Deque wrapper

    stack.push(startNode);

    while (!stack.isEmpty()) {
        String current = stack.pop();

        // In iterative DFS, we check if visited AFTER popping (unlike BFS)
        if (!visited.contains(current)) {
            visited.add(current);
            System.out.print(current + " ");

            // Push neighbours onto the stack
            // (Note: To match recursive output order, push in reverse)
            List<String> neighbours = adjList.getOrDefault(current, new ArrayList<>());
            for (int i = neighbours.size() - 1; i >= 0; i--) {
                String neighbour = neighbours.get(i);
                if (!visited.contains(neighbour)) {
                    stack.push(neighbour);
                }
            }
        }
    }
}

When to Use DFS vs BFS

Both algorithms visit every node ($O(V+E)$ time) and use $O(V)$ memory in the worst case. But their geometries are completely different.

Classic DFS Applications

1. Cycle Detection: If DFS ever encounters a node that is currently in the ongoing recursion stack, the graph has a cycle.
2. Topological Sorting: Used to determine dependencies (e.g., “Build package A before package B”). You run DFS and add nodes to a list only when they finish exploring.
3. Connected Components: To count how many separate “islands” exist in a graph, loop through every node, and run DFS on unvisited ones. Every DFS launch is exactly one component.
4. Solving Puzzles/Mazes: DFS combined with Backtracking is the standard way to solve Sudoku, N-Queens, or find paths through mazes.

Practice Problems

1. Max Area of Island – LeetCode #695 — Use DFS on a 2D grid to find the size of connected components.
2. Course Schedule – LeetCode #207 — A pure Cycle Detection problem using DFS.
3. Word Search – LeetCode #79 — A classic DFS Backtracking problem on a character grid.

What’s Next?

BFS finds the shortest path on unweighted graphs (where every edge costs 1). But what if edges have different costs? What if road A takes 5 minutes, but road B takes 20 minutes?

To find the absolute fastest route on a weighted graph, we need the most famous algorithm of them all: Dijkstra’s Shortest Path.