Depth-First Search (DFS) — Implement DFS using recursion or an explicit stack (intro)

Historical Context & Motivation

Long before computers existed, mathematicians were fascinated by the problem of navigating complex structures like mazes and networks. The core question was deceptively simple: given a starting point and a web of connected paths, how can you guarantee you visit every reachable location exactly once? This is the fundamental problem that Depth-First Search (DFS) was designed to solve. DFS is one of the most important algorithms in all of computer science, forming the backbone of solutions ranging from maze generation to social-network analysis.

The central question DFS addresses is this: given a graph — a collection of nodes (also called vertices) connected by edges — how can we systematically visit every reachable node? Unlike its sibling algorithm Breadth-First Search (BFS), DFS commits to one path as far as it can go before backtracking to explore alternatives. This "go deep first" strategy makes DFS ideal for detecting cycles, solving puzzles, and exploring tree structures.

Core Principles & Definitions

Before diving into code, you need to understand the foundational ideas behind DFS. At its heart, the algorithm relies on a simple rule: always explore the deepest unexplored neighbor first. When you reach a dead end — a node whose neighbors have all been visited — you backtrack to the most recent node that still has unvisited neighbors. This behavior maps perfectly onto a data structure called a stack, which follows the Last-In, First-Out (LIFO) principle.

Visual Explanation — How DFS Traverses a Graph

The following diagram shows a simple undirected graph with six nodes labeled A through F. The numbered arrows show the order in which DFS visits each node when starting from node A. Notice how the algorithm goes as deep as possible along one branch before backtracking to explore other branches.

Notice the key pattern: DFS doesn't visit node C (which is directly connected to A) until after it has fully explored the branch starting at B. This is the defining characteristic of depth-first traversal. The algorithm commits fully to one branch before exploring siblings. Compare this to how you might read a book: DFS reads the entire first chapter, including all sub-sections, before moving to chapter two.

How DFS Works — Recursion vs. Explicit Stack

There are two standard ways to implement DFS in Java. The first uses recursion, where the method calls itself for each unvisited neighbor. The Java runtime maintains an internal call stack that automatically handles the backtracking. The second approach uses an explicit stack — a Stack<Integer> object — where you manually push and pop nodes. Both approaches produce the same traversal, but they have different trade-offs that we'll explore.

The Recursive DFS Algorithm

The recursive version is elegant and compact. Here is the pseudocode that drives every recursive DFS implementation:

The Iterative DFS Algorithm (Explicit Stack)

Time and Space Complexity

Java Implementation — Line by Line

Now let's translate the pseudocode into real Java. We'll represent the graph using an adjacency list — a Map<Integer, List<Integer>> where each key is a node and its value is a list of neighboring nodes. This is the most common graph representation you'll encounter in Java.

Let's break down the critical parts. In the recursive version, the line visited.add(node) marks the current node immediately upon entry, preventing the algorithm from revisiting it. The for loop iterates over all neighbors, and the recursive call dfsRecursive(graph, neighbor, visited) dives one level deeper. When that call returns, the loop continues to the next neighbor — this is the backtracking step.

In the iterative version, the while (!stack.isEmpty()) loop replaces the recursion. After popping a node, we check if it's already visited (since the same node could have been pushed multiple times by different neighbors). The getOrDefault method is a safe way to retrieve the neighbor list — it returns an empty list if the node has no outgoing edges, avoiding a NullPointerException.

Worked Example — Tracing DFS Step by Step

Let's trace the iterative DFS algorithm on a small graph with 5 nodes: 0, 1, 2, 3, and 4. The edges are: 0−1, 0−2, 1−3, 1−4, and 2−4. We start from node 0.

DFS: Recursion vs. Stack — Strengths & Limitations

Both implementations have the same time and space complexity, but they behave differently in practice. The table below summarizes the key trade-offs you should consider when choosing between them.

Connection to Advanced Topics

DFS is not just a standalone algorithm — it's a building block for many advanced techniques in computer science. Once you're comfortable with basic DFS traversal, you can extend it to solve significantly harder problems. The table below previews some of these connections.

You should also know that DFS has a counterpart called Breadth-First Search (BFS), which uses a queue instead of a stack. BFS explores all neighbors at the current depth before going deeper, making it ideal for finding the shortest path in unweighted graphs. Together, DFS and BFS form the two fundamental graph traversal strategies that you'll use throughout your computer science journey.

Practice Problems

Summary — Depth-First Search in Java