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

SECTION 1

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.

1735 • Euler and the Königsberg Bridges

Leonhard Euler studied whether one could walk across all seven bridges of Königsberg exactly once, founding graph theory — the mathematical field that DFS operates within.

1882 • Trémaux's Maze Algorithm

French mathematician Charles Pierre Trémaux described a strategy for solving mazes by marking paths as explored — an early form of depth-first traversal using backtracking.

1945 • Konrad Zuse's Plankalkül

German engineer Konrad Zuse designed one of the first programming languages, which included concepts for iterating over graph-like structures, paving the way for algorithmic graph traversal.

1972 • Tarjan's DFS Applications

Robert Tarjan published groundbreaking algorithms using DFS to find strongly connected components and articulation points in graphs, earning him the Turing Award.

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.

SECTION 2

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.

Graph

A collection of nodes (vertices) and edges (connections between nodes). Graphs can be directed or undirected, and they model relationships like friendships, roads, or dependencies.

Stack (LIFO)

A data structure where the last element added is the first one removed. Think of a stack of plates — you always grab the top one. DFS uses this structure to remember which node to return to.

Recursion

A technique where a method calls itself. Each recursive call automatically uses the system's call stack, making recursion a natural fit for DFS without explicitly creating a stack object.

Visited Set

A set that tracks which nodes have already been explored. Without it, DFS could loop forever in a graph that contains cycles — paths that lead back to a previously visited node.

Backtracking

When DFS reaches a dead end (no unvisited neighbors), it returns to the previous node and tries a different path. This is the "depth-first" part — explore fully, then retreat.

✦

KEY TAKEAWAY

Imagine you're exploring a cave system with many branching tunnels. DFS is like always choosing to go deeper into the next tunnel until you hit a dead end, then walking back to the last fork and trying a different tunnel. You carry a piece of chalk to mark tunnels you've already explored (the visited set), and your memory of which forks to return to is the stack.

SECTION 3

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.

Starting from node A, DFS goes deep along A → B → D → E, backtracks when E has no unvisited neighbors, returns to D, then to B, explores C, backtracks again to A, and finally visits F. The dashed arrows and circled numbers show the traversal order.

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.

SECTION 4

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:

RECURSIVE DFS PSEUDOCODE

DFS(node, visited): mark node as visited for each neighbor of node: if neighbor not in visited: DFS(neighbor, visited)

node = the current vertex being explored. visited = a Set that tracks which nodes have been seen. neighbor = a node directly connected to the current node by an edge.

The Iterative DFS Algorithm (Explicit Stack)

ITERATIVE DFS PSEUDOCODE

DFS(start): create empty Stack, push start create empty visited Set while stack is not empty: node = stack.pop() if node not in visited: mark node as visited for each neighbor of node: if neighbor not in visited: stack.push(neighbor)

stack = an explicit Stack object that replaces the call stack. pop() removes the top element (LIFO order). push() adds a neighbor to the top of the stack.

Time and Space Complexity

TIME COMPLEXITY

T(V, E) = O(V + E)

V = number of vertices (nodes). E = number of edges. Each vertex is visited once and each edge is examined once, giving linear time.

SPACE COMPLEXITY

S(V) = O(V)

In the worst case, all V nodes could end up on the stack (or call stack) at once — for example, in a straight-line graph with no branching.

SECTION 5

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.

Both implementations achieve the same goal. The recursive version (left) is shorter but risks a StackOverflowError on very deep graphs. The iterative version (right) uses a Stack object on the heap, which can grow larger than the call stack.

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.

💡

Java Import Tip

For the iterative version, you'll need import java.util.Stack; and import java.util.HashSet;. For the graph itself, use import java.util.Map;, import java.util.HashMap;, and import java.util.List;. Modern Java also supports Deque<Integer> with ArrayDeque as a faster alternative to Stack.

SECTION 6

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.

Iterative DFS Trace — Starting from Node 0

1
Step 1 — Initialize

Create an empty stack and push the start node 0. Create an empty visited set. Stack: [0]. Visited: {}.

Stack = [0], Visited = {}
2
Step 2 — Pop 0, Mark Visited, Push Neighbors

Pop 0 from the stack. It's not in visited, so mark it visited and print it. Node 0's neighbors are 1 and 2. Push both onto the stack. Stack: [1, 2] (2 is on top). Visited: {0}.

Output so far: 0
3
Step 3 — Pop 2, Mark Visited, Push Neighbors

Pop 2 (top of stack). Not visited, so mark it. Node 2's neighbor is 4. Push 4. Stack: [1, 4]. Visited: {0, 2}.

Output so far: 0 2
4
Step 4 — Pop 4, Mark Visited, Push Neighbors

Pop 4. Not visited, so mark it. Node 4's neighbors are 1 and 2. Push both, but 2 is already visited — it will be skipped when popped. Stack: [1, 1, 2]. Visited: {0, 2, 4}.

Output so far: 0 2 4
5
Step 5 — Pop 2 (skip), Pop 1, Pop 1 (skip) — Continue Until Empty

Pop 2 — already visited, skip. Pop 1 — not visited, mark it, print it. Push 1's neighbors 3 and 4. Pop 4 — already visited, skip. Pop 3 — not visited, mark it, print it. Pop 1 — already visited, skip. Stack is now empty and the algorithm terminates.

Final output: 0 2 4 1 3

⚠

Order May Vary

The exact traversal order depends on which neighbor is pushed first. If we had pushed 2 before 1 in Step 2, we'd visit 1 before 2. The recursive version also depends on the order that getOrDefault returns neighbors. Both are valid DFS traversals as long as the depth-first property holds.

SECTION 7

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.

Criterion	Recursive DFS	Iterative DFS (Explicit Stack)
Code Length	Short and elegant — about 8−10 lines	Slightly longer — about 12−15 lines
Stack Type	Implicit (Java call stack, limited to ~5,000−10,000 frames)	Explicit (heap-allocated, can grow much larger)
Risk of Overflow	StackOverflowError on deep graphs	Handles deep graphs safely
Ease of Understanding	More intuitive if you're comfortable with recursion	Easier to debug and trace step by step
Best For	Trees, small graphs, coding interviews	Large graphs, production code, avoiding recursion limits

Comparison of Recursive and Iterative DFS Implementations

✦

KEY TAKEAWAY

Think of the recursive approach as using a mental bookmark — your brain (the call stack) naturally remembers where you left off. The iterative approach is like using sticky notes — you physically write down every place you need to come back to. For small books (graphs), mental bookmarks are fine. For a massive library, you'll want those sticky notes to avoid forgetting.

SECTION 8

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.

Basic DFS Concept	Advanced Application
Visiting all reachable nodes	Connected components — run DFS from each unvisited node to find isolated clusters
Backtracking after dead ends	Topological sort — order tasks by dependencies using post-order DFS
Tracking visited nodes	Cycle detection — detect if a graph contains loops using a "currently exploring" state
Exploring neighbors recursively	Maze solving and pathfinding — find a path from start to goal in a grid
Depth-first traversal order	Tarjan's algorithm — find strongly connected components in directed graphs

From Basic DFS to Advanced Graph Algorithms

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.

SECTION 9

Practice Problems

Question 1: CONCEPTUAL

Explain in your own words why DFS is called "depth-first." What data structure makes DFS naturally explore deep before exploring wide, and why does that structure produce this behavior?

Show answer

DFS is called "depth-first" because it always explores as far down one path as possible before backtracking to try another. The stack (whether the implicit call stack in recursion or an explicit Stack object) produces this behavior because of its Last-In, First-Out (LIFO) property. When a new neighbor is added, it goes on top and is processed next, pushing the algorithm deeper before returning to earlier nodes. If DFS used a queue (FIFO) instead, it would become Breadth-First Search.

Question 2: BASIC CALCULATION

Consider a graph with 4 nodes: 0 → 1, 0 → 3, 1 → 2. If you run recursive DFS starting from node 0 and the neighbor list for each node is in ascending order, write the exact sequence of nodes visited.

Show answer

Starting at node 0, DFS visits 0, then checks neighbors in order: 1 comes first, so it recurses to 1. From 1, the only unvisited neighbor is 2, so it recurses to 2. Node 2 has no unvisited neighbors, so it backtracks to 1, then to 0. Node 0's remaining unvisited neighbor is 3, so it visits 3. The traversal order is: 0, 1, 2, 3. Notice that DFS fully explored the 0 → 1 → 2 branch before visiting node 3.

Question 3: INTERMEDIATE

In the iterative DFS implementation, why do we check if (!visited.contains(node)) after popping from the stack, instead of before pushing? What would go wrong if we only checked before pushing?

Show answer

In iterative DFS, the same node can be pushed onto the stack multiple times by different neighbors before it is actually popped and processed. For example, if nodes A and B are both neighbors of node C, both might push C onto the stack before either processes it. Checking after popping ensures that even if C appears multiple times on the stack, it's only visited once. If you only checked before pushing, you'd prevent duplicates from the same parent, but you'd miss the case where two different parents both push the same child simultaneously. The post-pop check is the safest and most correct approach.

Question 4: APPLIED

You are building a social network app. Each user is a node, and friendships are undirected edges. Given a user ID, you need to find all users who are in the same friend group (connected component). Write Java pseudocode (or actual Java) using recursive DFS to return a Set<Integer> of all user IDs in the same component as the given user.

Show answer

You'd create a method like Set<Integer> findFriendGroup(Map<Integer, List<Integer>> graph, int userId) that initializes a HashSet<Integer> visited and calls a recursive helper dfs(graph, userId, visited). The helper marks the node visited, then loops through each neighbor — if the neighbor isn't visited, it recurses. After the initial DFS call returns, the visited set contains every user reachable from userId, which is exactly the friend group. This works because DFS explores all reachable nodes from a starting point, which is the definition of a connected component.

Question 5: CRITICAL THINKING

A student claims that for any graph, recursive DFS and iterative DFS will always visit nodes in the exact same order. Is this claim true or false? Justify your answer by considering how each approach processes a node's neighbors, and construct a small example where the orders might differ.

Show answer

The claim is false. Consider a node with neighbors [A, B, C]. In recursive DFS, the for-loop visits A first, recursing immediately into A's subtree. In iterative DFS, all three neighbors are pushed onto the stack in order, meaning C ends up on top and is popped first. So iterative DFS would visit C before A. To make them produce the same order, you'd need to push neighbors in reverse order in the iterative version. For example, with a graph where node 0 connects to [1, 2], recursive DFS visits 0, 1, 2 while iterative DFS visits 0, 2, 1 (since 2 is pushed last and popped first). This subtle difference is important to understand when the specific traversal order matters.

SUMMARY

Summary — Depth-First Search in Java

Summary

Depth-First Search (DFS) is a fundamental graph traversal algorithm that explores as far as possible along each branch before backtracking. It relies on a stack (LIFO) data structure — either the implicit call stack through recursion, or an explicit Stack object in an iterative loop. A visited set prevents infinite loops in graphs with cycles.

Both implementations run in O(V + E) time and O(V) space. The recursive version is more concise but risks StackOverflowError on deep graphs. The iterative version handles larger graphs safely. DFS is the foundation for advanced algorithms including topological sort, cycle detection, connected components, and maze solving. In Java, graphs are typically represented as an adjacency list using Map<Integer, List<Integer>>.