NUHMAN.com

Depth-First Search (DFS) is a classic algorithm for exploring graphs and trees. Unlike BFS, which explores neighbors level by level, DFS dives deep into each branch before backtracking. DFS can be implemented recursively or iteratively (using a stack).

In this article, we’ll walk through both DFS implementations in Java using an adjacency list.

1. Graph Structure Recap (Adjacency List)

We'll be using a Map<Vertex, List<Vertex>> to represent our graph. Each Vertex holds a label and overrides equals() and hashCode().

Vertex Class

java

import java.util.Objects;

public class Vertex {
    private String label;

    public Vertex(String label) {
        this.label = label;
    }

    public String getLabel() {
        return label;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (!(o instanceof Vertex)) return false;
        Vertex vertex = (Vertex) o;
        return Objects.equals(label, vertex.label);
    }

    @Override
    public int hashCode() {
        return Objects.hash(label);
    }

    @Override
    public String toString() {
        return label;
    }
}

2. DFS Recursive Implementation

Recursive DFS is simple and elegant. We use a helper function to recursively visit unvisited neighbors.

DFS with Recursion

java

// Inside Graph class

private void dfsRecursive(Vertex vertex, Set<Vertex> visited) {
    visited.add(vertex);
    System.out.print(vertex + " ");

    for (Vertex neighbor : adjVertices.get(vertex)) {
        if (!visited.contains(neighbor)) {
            dfsRecursive(neighbor, visited);
        }
    }
}

public void dfs(String startLabel) {
    Vertex startVertex = new Vertex(startLabel);
    if (!adjVertices.containsKey(startVertex)) {
        System.out.println("Vertex not found in the graph.");
        return;
    }

    Set<Vertex> visited = new HashSet<>();
    dfsRecursive(startVertex, visited);
    System.out.println();
}

3. DFS Iterative Implementation (Using Stack)

We can simulate the recursion stack explicitly using Java’s Stack class.

DFS with Stack

java

// Inside Graph class

public void dfsIterative(String startLabel) {
    Vertex startVertex = new Vertex(startLabel);
    if (!adjVertices.containsKey(startVertex)) {
        System.out.println("Vertex not found in the graph.");
        return;
    }

    Set<Vertex> visited = new HashSet<>();
    Stack<Vertex> stack = new Stack<>();
    stack.push(startVertex);

    while (!stack.isEmpty()) {
        Vertex vertex = stack.pop();
        if (!visited.contains(vertex)) {
            visited.add(vertex);
            System.out.print(vertex + " ");

            for (Vertex neighbor : adjVertices.get(vertex)) {
                if (!visited.contains(neighbor)) {
                    stack.push(neighbor);
                }
            }
        }
    }

    System.out.println();
}

4. Full Example Usage

Here’s how you can create a graph and run both DFS methods:

java

public class Main {
    public static void main(String[] args) {
        Graph graph = new Graph();
        graph.addVertex("A");
        graph.addVertex("B");
        graph.addVertex("C");
        graph.addVertex("D");
        graph.addVertex("E");

        graph.addEdge("A", "B");
        graph.addEdge("A", "C");
        graph.addEdge("B", "D");
        graph.addEdge("C", "D");
        graph.addEdge("D", "E");

        graph.printGraph();

        System.out.println("DFS starting from vertex A (Recursive):");
        graph.dfs("A");

        System.out.println("DFS starting from vertex A (Iterative):");
        graph.dfsIterative("A");
    }
}

Output

mathematica

A -> B C 
B -> A D 
C -> A D 
D -> B C E 
E -> D 
DFS starting from vertex A (Recursive):
A B D C E 
DFS starting from vertex A (Iterative):
A C D E B 

Note: DFS traversal order can vary depending on the order neighbors are added in the adjacency list.

5. How DFS Works

ApproachMechanismTools UsedRecursive DFSUses function call stack to go deepRecursion, HashSetIterative DFSManually manages stack for traversalStack, HashSet

DFS is useful for exploring connectivity, detecting cycles, performing topological sorting, and solving maze-like problems.

6. Applications of DFS

• Cycle detection in graphs
• Topological sorting
• Maze solving algorithms
• Pathfinding in AI
• Finding connected components

Final Thoughts

DFS is a fundamental part of any Java developer's graph toolkit. Whether you're exploring graphs recursively or using a stack, mastering DFS is essential for many technical interview questions and real-world applications.