DFS Algorithm in Java

DFS algorithm is a traversal algorithm which is defined as a search algorithm which is abbreviated as depth-first search, which is known as graph algorithm also as it searches in the tree structure which looks like graph structure and hence it starts from the root and traverses along with the graph below with different branches. In general, DFS algorithm in Java is defined as a traversal algorithm that traverses in tree or graph structure that starts from the root node at the initial point and goes deep with each branch till it reaches the last node of any last branch such search is known as depth-first search and this provides 3 different ways of DFS such as preorder, inorder, and postorder traversal searches.

Start Your Free Software Development Course

Web development, programming languages, Software testing & others

Algorithm:

DFS is a uniformed algorithm that results in non-optimal solutions, and the DFS algorithm works as follows:

Step 1: Start with the root node of any given graph or tree.

Step 2: Now considering the root node as the first node of the graph and place this node at the top of the stack or list.

Step 3: Now look for adjacent nodes of the root node, which was the first node, and add these adjacent nodes to the other list of adjacent nodes list.

Step 4: Then go on adding the adjacent nodes of each node in the stack or list after the root node.

Step 5: Continue step3 to 4 until you reach the last branch’s end node in the graph or the list of adjacent nodes becomes empty.

Therefore, the DFS algorithm in Java is one of the traversal search algorithms that search deeply until the end node from the initial node. However, sometimes it is confusing when you traverse through the graph, whether through a left branch or right branch; to resolve this, there are 3 different types of DFS preorder, inorder, and postorder for traversing through the tree according to the specified order.

How does the DFS algorithm work with Examples?

In Java, the DFS algorithm works according to the algorithm described above. DFS algorithm for non directed graph will start from root node by first placing this root node in the one stack which can be considered as the visited stack which holds the nodes that are visited, and then place all the adjacent nodes of the root node in this visited stack where the root node is present. Then traverse through the graph and then find an adjacent node of each root’s adjacent node and continue till the last node of the graph and traversing these nodes by placing all the nodes in another stack so after completing the search, the visited stack is displayed which gives the nodes that have been traversed through the graph.

Example #1

Now let us see a simple DFS algorithm example which is implemented in Java programming language on a disconnected graph.

Code:

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
class vertex
{
int root, dest;
public vertex(int root, int dest)
{
this.root = root;
this.dest = dest;
}
}
class graphstruc
{
List<List<Integer>> adjList = null;
graphstruc(List<vertex> v, int N)
{
adjList = new ArrayList<>();
for (int i = 0; i < N; i++) {
adjList.add(new ArrayList<>());
}
for (vertex e: v)
{
int src = e.root;
int dest = e.dest;
adjList.get(src).add(dest);
adjList.get(dest).add(src);
}
}
}
class Main
{
public static void DFS(graphstruc graph, int v, boolean[] d)
{
d[v] = true;
System.out.print(v + " ");
for (int u: graph.adjList.get(v))
{
if (!d[u]) {
DFS(graph, u, d);
}
}
}
public static void main(String[] args)
{
List<vertex> v = Arrays.asList(
new vertex(1, 2), new vertex(1, 7), new vertex(1, 8),
new vertex(2, 3), new vertex(2, 6), new vertex(3, 4),
new vertex(3, 5), new vertex(8, 9), new vertex(8, 12),
new vertex(9, 10), new vertex(9, 11), new vertex(10, 12),
new vertex(10, 13), new vertex(11, 14)
);
final int N = 15;
graphstruc g = new graphstruc(v, N);
boolean[] d = new boolean[N];
System.out.println("Demonstration of Depth First Search algorithm in Java is as follows:");
for (int i = 0; i < N; i++)
{
if (!d[i]) {
DFS(g, i, d);
}
}
}
}

Output:

In the above example, we first are defining a class vertex in which we will declare the root and destination vertex in the graph where this class vertex stores the vertices of the graph. Then we define the class graphstruc to declare the adjacent vertices of the root node and add these adjacent nodes in the list. We are storing the adjacent vertices and later adding the adjacent vertices of these vertices in the list. Then to perform DFS, we are declaring a class DFS through which we will identify the current node from the given graph, and we go on identifying adjacent nodes of each node and add in the adjacent list nodes. Then lastly, in the main class, we will define a list of graph vertices as an array along with a total number of nodes, and after calling the DFS function, it will display the list in the DFS search list as shown in the above screenshot, which is the output.

Example #2

Now let us see the DFS implementation with different types of traversal orders such as preorder, inorder and postorder traversal in Java. In the below, we will see preorder implementation in Java.

Code:

class vertex
{
int data;
vertex l, r;
public vertex(int k)
{
data = k;
l = r = null;
}
}
class Main
{
public static void preorder(vertex root)
{
if (root == null) {
return;
}
System.out.print(root.data + " ");
preorder(root.l);
preorder(root.r);
}
public static void main(String[] args)
{
vertex root = new vertex(2);
root.l = new vertex(3);
root.r = new vertex(1);
root.l.l = new vertex(6);
root.r.l = new vertex(4);
root.r.r = new vertex(5);
root.r.l.l = new vertex(8);
root.r.l.r = new vertex(7);
preorder(root);
}
}

Output:

In the above example is also similar to the previous example where here the only difference is we are defining the traverse orders in the DFS algorithm. In this, we are defining only the preorder traversal order, which, when defined it will traverse the depth-first graph in order as the root node, left node, and right node. Therefore here in this, we have declared node 2 as the root node and node 3 as the left node and node 6 as a right node, and so on. The output is as shown in the above screenshot.

Conclusion

This article concludes that the DFS algorithm in Java is a traversal algorithm to find or search the graph deeply until the last node is visited. The time complexity for the DFS algorithm is usually represented in O(E+V), where E for edges and V for vertices of the graph. There are many different applications of the DFS algorithm based on its traversal orders that are classified as inorder, preorder, and postorder DFS traversal through the graph.

The above is the detailed content of DFS Algorithm in Java. For more information, please follow other related articles on the PHP Chinese website!