Depth First Search (DFS) Java Program

In this tutorial you will learn about implementation of Depth First Search in Java with example.

To traverse in trees we have traversal algorithms like inorder, preorder, postorder. Same way to traverse in graphs we have mainly two types of algorithms called DFS (Depth First Search) and BFS (Breadth First Search).

In Depth First Search traversal we try to go away from starting vertex into the graph as deep as possible. We may face the case that our search never ends because, unlike tree graph may contains loops. Since this reason we maintain a Boolean array which stores whether the node is visited or not.

Also Read: Breadth First Search (BFS) Java Program

Initially all vertices are marked as unvisited, that means Boolean array contain all zeros. DFS algorithm starts form a vertex “u” from graph. Starting with that vertex it considers all edges to other vertices from that vertex. While going when a new node encountered that corresponding node status in Boolean array will be changed to 1. That unvisited node becomes our new node and we again start our problem of DFS with that node. When we came to already visited node we should do backtracking. This entire process terminates when backtracking drag us to the start vertex where we started initially.

Depth First Search Example

dfs 1

Here initially no node visited we start DFS from node A.

dfs 2

Red color node represents node already visited.

Blue color node represents node not yet visited.

After visiting node A corresponding array value changed to 1.

dfs 3

Here after node A, node B visited.

dfs 4

Node C visited after node B and corresponding value in Boolean array changed to 1.

dfs 5

Node E visited and array updated in its correct position.

dfs 6

All nodes visited. But process of DFS not stopped here.

Now From D it tries to explore any non-visited node. But not able to find non-visited node from D. So it backtrack to node E.

dfs 7

Backtracking to node E from node D.

Next node E tries to explore non-visited vertex. But it not able to find non-visited vertex. So it backtrack to Vertex C.

dfs 8

Backtracking to Vertex C from Vertex E.

Now Vertex C also don’t have any non-visited vertex so it backtrack to Vertex B.

dfs 9

Backtracking to vertex B from vertex C.

Now vertex B do backtracking to vertex A since it don’t have any non-visited vertex.

dfs 10

Backtracking to Vertex A from Vertex B.

Now the termination condition occurred.

We can stop our DFS process because we reached where we started.

Note: When graph is not connected then we should check Boolean array that all nodes visited or not. If not visited then start DFS from that node. Here we will see the code which will run on disconnected components also.

Depth First Search (DFS) Java Program

Below program shows implementation of dfs in Java.

Output

1 2 5 6 4 7 8 3 9

Applications of DFS

  • Implementing Topological sorting
  • Solving different puzzles
  • Checking graph connected or not
  • To detect cycle in graph
  • To test graph is bipartite or not
  • To find spanning trees and forests.
  • To find connected components of graph
  • To find cut vertices of the graph

Comment below if you have queries or found any information incorrect in above Depth First Search Java program.

Leave a Reply

Your email address will not be published. Required fields are marked *