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

``````
``````

`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

``````
``````

`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

``````
``````

`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

``````
``````

`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