Java Program to Implement DFS (Depth First Search)

A Java program to implement DFS uses a recursive method that visits a node, marks it visited, and then recursively visits all its unvisited neighbors, like dfs(int node, boolean[] visited, List[] graph).

Examples

InputGraph edges: 0-1, 0-2, 1-2, 2-0, 2-3, 3-3; Start node: 2

OutputDFS traversal starting from node 2: 2 0 1 3

InputGraph edges: 0-1, 1-2; Start node: 0

OutputDFS traversal starting from node 0: 0 1 2

InputGraph edges: 0-1; Start node: 1

OutputDFS traversal starting from node 1: 1

How to Think About It

To implement DFS, think of starting at a node, marking it as visited, then exploring each connected node that hasn't been visited yet. This repeats recursively until all reachable nodes are visited, similar to exploring branches of a tree one by one.

Algorithm

1

Create a graph representation using adjacency lists.

2

Initialize a visited array to keep track of visited nodes.

3

Start DFS from the given start node.

4

Mark the current node as visited and print it.

5

For each neighbor of the current node, if not visited, recursively call DFS on it.

Code

java

import java.util.*;

public class DFSExample {
    static void dfs(int node, boolean[] visited, List<Integer>[] graph) {
        visited[node] = true;
        System.out.print(node + " ");
        for (int neighbor : graph[node]) {
            if (!visited[neighbor]) {
                dfs(neighbor, visited, graph);
            }
        }
    }

    public static void main(String[] args) {
        int nodes = 4;
        List<Integer>[] graph = new ArrayList[nodes];
        for (int i = 0; i < nodes; i++) {
            graph[i] = new ArrayList<>();
        }
        graph[0].add(1);
        graph[0].add(2);
        graph[1].add(2);
        graph[2].add(0);
        graph[2].add(3);
        graph[3].add(3);

        boolean[] visited = new boolean[nodes];
        System.out.print("DFS traversal starting from node 2: ");
        dfs(2, visited, graph);
    }
}

Output

DFS traversal starting from node 2: 2 0 1 3 

Dry Run

Let's trace DFS starting from node 2 through the graph.

1

Start at node 2

Mark node 2 visited, print 2.

2

Visit neighbors of 2

Neighbors are 0 and 3. First visit 0.

3

At node 0

Mark 0 visited, print 0. Neighbors are 1 and 2. 2 already visited, visit 1.

4

At node 1

Mark 1 visited, print 1. Neighbor is 2, already visited.

5

Back to node 2

Next neighbor is 3. Visit 3.

6

At node 3

Mark 3 visited, print 3. Neighbor is 3 itself, already visited.

Step	Current Node	Visited Nodes	Output
1	2	[false, false, true, false]	2
2	0	[false, false, true, false]	2 0
3	1	[false, true, true, false]	2 0 1
4	3	[false, true, true, true]	2 0 1 3

Why This Works

Step 1: Mark node visited

We mark the current node as visited using visited[node] = true to avoid revisiting it.

Step 2: Print node

We print the node to show the order of traversal.

Step 3: Recursive calls

For each neighbor, if not visited, we call dfs recursively to explore deeper nodes.

Alternative Approaches

Iterative DFS using stack

java

import java.util.*;

public class DFSIterative {
    public static void dfs(int start, List<Integer>[] graph) {
        boolean[] visited = new boolean[graph.length];
        Stack<Integer> stack = new Stack<>();
        stack.push(start);
        while (!stack.isEmpty()) {
            int node = stack.pop();
            if (!visited[node]) {
                visited[node] = true;
                System.out.print(node + " ");
                for (int neighbor : graph[node]) {
                    if (!visited[neighbor]) {
                        stack.push(neighbor);
                    }
                }
            }
        }
    }

    public static void main(String[] args) {
        int nodes = 4;
        List<Integer>[] graph = new ArrayList[nodes];
        for (int i = 0; i < nodes; i++) {
            graph[i] = new ArrayList<>();
        }
        graph[0].add(1);
        graph[0].add(2);
        graph[1].add(2);
        graph[2].add(0);
        graph[2].add(3);
        graph[3].add(3);

        System.out.print("Iterative DFS starting from node 2: ");
        dfs(2, graph);
    }
}

Uses a stack instead of recursion, which can avoid stack overflow for very deep graphs.

DFS with adjacency matrix

java

public class DFSMatrix {
    static void dfs(int node, boolean[] visited, int[][] graph) {
        visited[node] = true;
        System.out.print(node + " ");
        for (int i = 0; i < graph.length; i++) {
            if (graph[node][i] == 1 && !visited[i]) {
                dfs(i, visited, graph);
            }
        }
    }

    public static void main(String[] args) {
        int[][] graph = {
            {0,1,1,0},
            {0,0,1,0},
            {1,0,0,1},
            {0,0,0,1}
        };
        boolean[] visited = new boolean[graph.length];
        System.out.print("DFS traversal starting from node 2: ");
        dfs(2, visited, graph);
    }
}

Uses a matrix to represent edges, simpler for small graphs but uses more memory.

Complexity: O(V + E) time, O(V) space

Time Complexity

DFS visits each vertex and edge once, so the time is proportional to the number of vertices plus edges, O(V + E).

Space Complexity

The space is mainly for the visited array and recursion stack, both proportional to the number of vertices, O(V).

Which Approach is Fastest?

Recursive and iterative DFS have similar time complexity; iterative avoids recursion overhead and stack overflow risk.

Approach	Time	Space	Best For
Recursive DFS	O(V + E)	O(V)	Simple code, small to medium graphs
Iterative DFS	O(V + E)	O(V)	Large graphs, avoid recursion limits
Adjacency Matrix DFS	O(V^2)	O(V^2)	Dense graphs or small graphs