In this article, you will learn to implement Depth First Search (DFS) algorithm on a graph by using Java with iterative and recursive approaches

Depth First Search (DFS) is an algorithm for traversing or searching for a graph. The algorithm starts at an arbitrary node and explores as far as possible along each branch before backtracking

Let's get started!

Problem

  • Give an undirected/directed graph G(V, E)

  • Write a Depth-First search algorithm to print out each vertex value exactly once

Example

For the above graph with 0 as the starting vertex, assuming that the left edges are chosen before the right edges, the DFS traversal order will be 0 -> 1 -> 3 -> 2 -> 4

Approach 1: Iterative

  • Use an array to track visited nodes to avoid processing a node more than once

  • Use a stack to track which nodes to visit next

import java.util.ArrayDeque;  
import java.util.Deque;

public class DFSByIterative {  
    static void dfsByIterative(GraphUndirectedByAdjacencyList g, int v) {
        boolean[] visited = new boolean[g.getV()];

        Deque<Integer> stack = new ArrayDeque<>();
        stack.push(v);

        while (!stack.isEmpty()) {
            v = stack.pop();

            if (!visited[v]) {
                visited[v] = true;
                System.out.printf("%d ", v);

                for(Integer w : g.getAdjacencyList().get(v)) {
                    stack.push(w);
                }
            }
        }
    }

    public static void main(String[] args) {
        GraphUndirectedByAdjacencyList g = new GraphUndirectedByAdjacencyList(5);
        g.addEdge(0, 2);
        g.addEdge(1, 2);
        g.addEdge(1, 0);
        g.addEdge(1, 3);
        g.addEdge(2, 4);

        dfsByIterative(g, 0);
    }
}

GraphUndirectedByAdjacencyList is defined in Graph Data Structure

  • Output
0 1 3 2 4  
  • Time complexity: O(V+E)

  • Space complexity: O(V)

Approach 2: Iterative with Color

  • Use a color array to track vertex states. Each vertex can have 3 states marked by color

    • White represents unvisited

    • Gray represents a visit in progress

    • Black represents visited

  • Use a stack to track which nodes to visit next

import java.util.ArrayDeque;  
import java.util.Deque;

public class DFSByIterativeWithColor {  
    static final int WHITE = 0, GRAY = 1, BLACK = 2;

    static void dfsByIterativeWithColor(GraphUndirectedByAdjacencyList g, int v) {
        int[] color = new int[g.getV()];

        Deque<Integer> stack = new ArrayDeque<>();
        stack.push(v);

        while (!stack.isEmpty()) {
            v = stack.pop();

            if (color[v] == WHITE) {
                color[v] = GRAY;
                System.out.printf("%d ", v);

                for(Integer w : g.getAdjacencyList().get(v)) {
                    stack.push(w);
                }

                color[v] = BLACK;
            }
        }
    }

    public static void main(String[] args) {
        GraphUndirectedByAdjacencyList g = new GraphUndirectedByAdjacencyList(5);
        g.addEdge(0, 2);
        g.addEdge(1, 2);
        g.addEdge(1, 0);
        g.addEdge(1, 3);
        g.addEdge(2, 4);

        dfsByIterativeWithColor(g, 0);
    }
}

GraphUndirectedByAdjacencyList is defined in Graph Data Structure

  • Output
0 1 3 2 4 
  • Time complexity: O(V+E)

  • Space complexity: O(V)

Approach 3: Recursive

  • Use an array to track visited nodes to avoid processing a node more than once

  • Instead of using a stack, the DFS algorithm calls to itself to explore unvisited vertices

public class DFSByRecursive {

    static void dfs(GraphUndirectedByAdjacencyList g, int v, boolean[] visited) {
        visited[v] = true;
        System.out.printf("%d ", v);

        for (Integer w : g.getAdjacencyList().get(v)) {
            if (!visited[w]) {
                dfs(g, w, visited);
            }
        }
    }

    static void traversal(GraphUndirectedByAdjacencyList g) {
        boolean[] visited = new boolean[g.getV()];

        for (int i = 0; i < g.getV(); i++) {
            if (!visited[i]) {
                dfs(g, i, visited);
            }
        }
    }

    public static void main(String[] args) {
        GraphUndirectedByAdjacencyList g = new GraphUndirectedByAdjacencyList(5);
        g.addEdge(0, 2);
        g.addEdge(1, 2);
        g.addEdge(1, 0);
        g.addEdge(1, 3);
        g.addEdge(2, 4);

        traversal(g);
    }
}

GraphUndirectedByAdjacencyList is defined in Graph Data Structure

  • Output
0 2 1 3 4 
  • Time complexity: O(V+E)

  • Space complexity: O(V)

Approach 4: Recursive with Color

  • Use a color array to track vertex states. Each vertex can have 3 states marked by color

    • White represents unvisited

    • Gray represents a visit in progress

    • Black represents visited

  • Instead of using a stack, the DFS algorithm calls to itself to explore White vertices

public class DFSByRecursiveWithColor {  
    static final int WHITE = 0, GRAY = 1, BLACK = 2;

    static void dfsByRecursiveWithColor(GraphUndirectedByAdjacencyList g, int v, int[] color) {
        color[v] = GRAY;
        System.out.printf("%d ", v);

        for (Integer w : g.getAdjacencyList().get(v)) {
            if (color[w] == WHITE) {
                dfsByRecursiveWithColor(g, w, color);
            }
        }
        color[v] = BLACK;
    }

    static void traversal(GraphUndirectedByAdjacencyList g) {
        int[] color = new int[g.getV()];

        for (int i = 0; i < g.getV(); i++) {
            if (color[i] == WHITE) {
                dfsByRecursiveWithColor(g, i, color);
            }
        }
    }

    public static void main(String[] args) {
        GraphUndirectedByAdjacencyList g = new GraphUndirectedByAdjacencyList(5);
        g.addEdge(0, 1);
        g.addEdge(0, 2);
        g.addEdge(1, 2);
        g.addEdge(1, 3);
        g.addEdge(2, 4);

        traversal(g);
    }
}

GraphUndirectedByAdjacencyList is defined in Graph Data Structure

  • Output
0 2 1 3 4 
  • Time complexity: O(V+E)

  • Space complexity: O(V)

Applications

  • Detect Cycle in a Directed Graph

    You can use DFS to detect a cycle in a directed graph. When visiting a vertex v and its adjacency vertices, if there is a back edge (w, v) which directs to v then that graph has a cycle

    Learn more

  • Implement Topological Sort with Directed Acyclic Graph

    Topological sort is an algorithm which takes a directed acyclic graph and returns a list of vertices in the linear ordering where each vertex has to precede all vertices it directs to

    Learn more