Trees and Graphs are pretty commonly used data structures in Java. Depth First Search (DFS) is one of the tree traversal algorithms. DFS starts by visiting a random unvisited node in the tree and goes deep into that branch before proceeding to explore the next branch.
In this example, I am going to explain Java Depth First Search algorithm and sample implementation.
1. DFS explained
In this section, I am going to explain DFS in simple steps.
To traverse a graph/tree in the DFS manner, we need a stack to maintain the nodes which are visited. Follow the below steps to traverse the graph/tree using DFS,
Before starting the traversal, we need to decide on the vertex node. Normally, we consider the head node as the vertex.
- Visit the unvisited adjacent node, push it onto the stack and mark as visited
- If the node doesn’t have any adjacent node, then pop it from the stack
- Repeat the steps till the stack is empty
The below pictures depict each iteration in DFS algorithm. All unvisited nodes in the tree are colored blue and visited ones are colored red.
- Initial State – no nodes are printed and stack contains root node
- Iteration 1 – Node A popped out and printed. Its children Node C and B are put on the stack.
- Iteration 2 – Node B is printed and we go on to visit its children. Node B’s children Node E and Node D are pushed on to the stack
- Iteration 4 – Current top of the stack Node D popped out and printed. Since it is a child node no other node to visit.
- Iteration 5- The current top of the stack is Node E. Node E is popped out and printed. Since node E is leaf node, no more node to visit and we continue to the next node
- Iteration 6 – Now Node is on top of the stack. It is popped and printed. Since it is not a child node, we push its children 9In this case we have only one child) pushed on to the stack.
- Iteration 7 – We pop the current top of stack Node F and print it. Since it is a leaf node no more nodes to push.
By this time we have visited all the nodes in the tree and we can see DFS traversal output.
If we are using it to search a particular node, then in every step we need to check if the popped out node is the goal node.
2. Java Example
In this section I am providing you a Java iterative approach to implement Depth First Search,
public class DepthFirstSearch {
List tree = new ArrayList();
public static void main(String[] args) {
Node nodeD = new Node("D", null, null);
Node nodeE = new Node("E", null, null);
Node nodeF = new Node("F", null, null);
Node nodeB = new Node("B", nodeD, nodeE);
Node nodeC = new Node("C", null, nodeF);
Node root = new Node("A", nodeB, nodeC);
DepthFirstSearch.executeDFS(root);
}
public static void executeDFS(Node root) {
Stack nodeStack = new Stack();
Node currentNode = root;
System.out.println("==================== DFS traversal =====================");
nodeStack.push(currentNode);
while(!nodeStack.isEmpty()) {
currentNode = nodeStack.pop();
System.out.println("-- " + currentNode.getData() + "--");
if(currentNode.getLeft() == null && currentNode.getRight() == null) {
continue;
}
else {
if(currentNode.getRight() != null) {
nodeStack.push(currentNode.getRight());
}
if(currentNode.getLeft() != null) {
nodeStack.push(currentNode.getLeft());
}
}
}
}
}
class Node {
String data;
Node left;
Node right;
public Node(String data, Node left, Node right) {
this.data = data;
this.left = left;
this.right = right;
}
public String getData() {
return this.data;
}
public Node getLeft() {
return this.left;
}
public Node getRight() {
return this.right;
}
}
Class Node represents the Linked List node structure. This holds the data, left child’s reference and right child’s reference.
Stack in the program contains the non-leaf visited node. Once we reach leaf node, we pop its parent from the stack and use it to traverse the unvisited children.
The output of the program is as follows,
3. Applications of DFS
Some of the uses of Depth First Search are as follows,
- DFS can be applied to find the cycle in a graph
- Can be useful to find the path between two nodes in tree or graph
- Can be applied to solve mazes
- To find out if the graph is strongly connected
- Designing a scheduling mechanism for the jobs based on their dependencies (topological sorting)
Dfs algorithms are increasingly gaining popularity in the Artificial Intelligence field. Often data is organized in graphs and Depth First Search becomes one of the algorithms of choice to find the path between the source and destination.
4. Download The Source Code
You can download the full source code of this example here: Depth First Search Java Example
