Implement Depth-First Search (DFS) Iteratively in Java

Introduction

Depth-First Search (DFS) is one of the most important algorithms in computer science, used for traversing graphs and trees. It explores as far as possible along a branch before backtracking, making it ideal for problems like maze solving, pathfinding, and analyzing network connectivity.

In most tutorials, DFS is introduced using recursion, but recursion can sometimes lead to stack overflow errors for large graphs. That’s where the iterative approach using a stack becomes useful. In this article, we’ll learn how to implement DFS iteratively in Java, step-by-step, with clear explanations and examples.

What Is Depth-First Search (DFS)?

DFS is a graph traversal algorithm that starts at a source node and explores as far as possible along each branch before backtracking. It uses a stack data structure, either implicitly (through recursion) or explicitly (through iteration).

Key Concepts

• DFS visits nodes deeply first, then goes back (backtracking).

• It can be applied to both graphs and trees.

• DFS can be implemented recursively or iteratively.

Common Use Cases

• Detecting cycles in a graph.

• Topological sorting.

• Solving mazes and puzzles.

• Pathfinding algorithms.

• Web crawlers.

DFS Recursive vs. Iterative Approach

While recursive DFS is simple to write, the iterative approach is more memory-efficient and avoids stack overflow for large datasets.

Aspect	Recursive DFS	Iterative DFS
Implementation	Uses function call stack	Uses explicit Stack data structure
Memory Usage	High (due to recursive calls)	Moderate (depends on stack size)
Ease of Writing	Easier	Slightly longer but safer
Risk of Stack Overflow	Yes	No
Control over Traversal	Limited	More control and flexibility

Step-by-Step: Iterative DFS in Java

To implement DFS iteratively, we’ll use a Stack from Java’s java.util package. Let’s break the implementation into clear steps.

Step 1. Represent the Graph

We’ll use an adjacency list to represent the graph, where each node stores its connected neighbors.

import java.util.*;

public class IterativeDFS {

    private int vertices; // number of vertices
    private LinkedList<Integer>[] adjacencyList;

    public IterativeDFS(int vertices) {
        this.vertices = vertices;
        adjacencyList = new LinkedList[vertices];
        for (int i = 0; i < vertices; i++) {
            adjacencyList[i] = new LinkedList<>();
        }
    }

    // Add edge (for undirected graph)
    void addEdge(int source, int destination) {
        adjacencyList[source].add(destination);
        adjacencyList[destination].add(source);
    }
}

Step 2. Implement the Iterative DFS Logic

Now, we’ll use a stack to perform DFS traversal. We’ll mark visited nodes to avoid re-visiting the same vertex.

void dfsIterative(int startNode) {
    boolean[] visited = new boolean[vertices];
    Stack<Integer> stack = new Stack<>();

    // Start DFS from the given node
    stack.push(startNode);

    while (!stack.isEmpty()) {
        int node = stack.pop();

        if (!visited[node]) {
            System.out.print(node + " ");
            visited[node] = true;
        }

        // Push all unvisited neighbors into the stack
        for (int neighbor : adjacencyList[node]) {
            if (!visited[neighbor]) {
                stack.push(neighbor);
            }
        }
    }
}

Step 3. Execute and Test the Program

Finally, let’s add a main method to test our iterative DFS algorithm.

public static void main(String[] args) {
    IterativeDFS graph = new IterativeDFS(5);

    graph.addEdge(0, 1);
    graph.addEdge(0, 2);
    graph.addEdge(1, 3);
    graph.addEdge(1, 4);

    System.out.println("DFS traversal (iterative): ");
    graph.dfsIterative(0);
}

Output

DFS traversal (iterative):
0 2 1 4 3

Note: The order may vary depending on the adjacency list order.

How the Iterative DFS Works

1. Start with the given node (e.g., 0) and push it into the stack.

2. Pop the top node and mark it as visited.

3. Process the node (print or store it).

4. Push all unvisited neighbors of the node into the stack.

5. Repeat steps 2–4 until the stack becomes empty.

This approach ensures that we explore deep paths first, just like recursive DFS.

Example Visualization

Let’s consider the following graph:

0 — 1 — 3
|    \
|     4
2

Adjacency list representation:

0: [1, 2]
1: [0, 3, 4]
2: [0]
3: [1]
4: [1]

DFS traversal starting from node 0 → 0 → 2 → 1 → 4 → 3

Advantages of Iterative DFS in Java

• ✅ No stack overflow: Handles large graphs without recursion limits.

• ✅ Better control: You can easily modify the stack-based approach to stop early or add conditions.

• ✅ Easier debugging: The stack content can be inspected at any time.

• ✅ Efficient for dense graphs.

Common Mistakes to Avoid

1. Not marking nodes as visited: This can cause an infinite loop.

2. Adding visited nodes to stack multiple times: Check before pushing.

3. Using the wrong data structure: Queue vs. Stack – remember, DFS requires a Stack, while BFS uses a Queue.

4. Forgetting backtracking logic: DFS explores as far as possible before backtracking.

Real-World Applications of DFS

DFS is widely used in software systems and algorithms:

• 🔹 Pathfinding algorithms (e.g., maze solvers)

• 🔹 Detecting cycles in directed/undirected graphs

• 🔹 Topological sorting

• 🔹 Solving puzzles like Sudoku

• 🔹 Web crawlers and dependency resolution systems

Summary

Depth-First Search (DFS) is a foundational algorithm in computer science. Implementing DFS iteratively in Java using a stack offers greater flexibility, avoids recursion limits, and improves efficiency for large graphs. This approach is especially useful in professional-grade applications where performance and control are critical.