Depth-First Search or DFS for a Graph Data Structure

By | July 22, 2020

In post talks about Depth-First Search or DFS for a Graph Data Structure with example

To solve problems on graphs, we need a mechanism for traveling the graph. graph traversal algorithms are usually called Graph Search Algorithms. like trees traversal algorithms( inorder, preorder, and level order traversals), Graph Search algorithms can be thought of As starting at some source vertex in a graph and searching the graph by going through the edges and marking the vertices. We have mainly two search algorithms for traveling the graphs

Depth-First Search(DFS)  is a method to explore a tree or graph.  In a DFS   We go as deep as possible down one path before backing up and trying a  different one. DFS algorithm works in a manner similar to the preorder traversal of the trees. like preorder traversal internally this algorithm also using stack.

In this post, we will learn How to write a Java program to do a Binary tree traversal using Depth-First Search (DFS).

In the previous post, Binary Tree Traversal Using Breadth-First Search, we already saw Java implementation for binary tree traversal using Breadth-First Search.

Now we will see How to implement for the binary tree traversal using Depth-First search.

Contrary to the Breadth-First Search (BFS) where nodes within the same level are visited first in Depth-First search traversal is done by moving to the next level of nodes. Control moves to the deepest node and then come back to the parent node when the dead-end is reached.

There are several orderings for Depth-First search of a binary tree- in-order, pre-order, and post-order which are easy to implement using recursion. Apart from that, you can also write a Depth-First search program using a stack in a non-recursive way. So, in this post, we’ll see Recursive Java implementation of in-order, pre-order and post-order traversal of a binary tree as well as iterative (non-recursive) Java implementation.

Binary tree In-order traversal Java program

The logic for In-order traversal of the binary search tree is as follows-

  • Recursively traverse the left subtree.
  • Visit the root node
  • Recursively traverse the right subtree

Note that in-order traversal of the binary search tree visits the nodes in ascending order so in-order traversal is also used for tree sort.

Binary tree Pre-order traversal Java program

The logic for pre-order traversal of the binary search tree is as follows-

  • Visit the root node
  • Recursively traverse the left subtree.
  • Recursively traverse the right subtree

Binary tree post-order traversal Java program

The logic for post-order traversal of the binary search tree is as follows-

  • Recursively traverse the left subtree.
  • Recursively traverse the right subtree
  • Visit the root node

Depth-first search recursive Java program

Below is the complete Java source for traversing a binary tree using Depth-First Search. This program shows the recursive methods for in-order traversal, pre-order traversal, and post-order traversal.

The output of this program:

Binary tree in-order traversal:
10 25 28 30 32 38 60 61 70 85
Binary tree post-order traversal:
10 28 25 32 38 30 61 85 70 60
Binary tree pre-order traversal:
60 30 25 10 28 38 32 70 61 85

Depth-first search Non-Recursive Java program

To write a Java program for Depth-First Search of a binary tree using a non-recursive method a stack is used as a stack data structure is used. Iterative approach implementation for in-order and pre-order traversal is easy to understand.

Iterative implementation for post-order traversal of a binary tree is a bit complex, as you can see in the recursive method the statement to display is after the recursive calls in post-order traversal which makes iterative implementation a bit complex.

Here post-order traversal iterative implementation is done using two stacks. In the first stack, you add root, left, right, and then add root first in the second stack and then the additional order would be right and left in the second stack when popping from the first stack. After that pop from the second stack would give you the post order of left, right, and root.

Here is a complete Java source code for traversing a binary tree using Depth-First Search. In the program, there are iterative methods for in-order traversal, pre-order traversal, and post-order traversal where the stack is used as an auxiliary data structure.

The output of this program:

Binary tree in-order traversal:
10 25 28 30 32 38 60 61 70 85
Binary tree post-order traversal:
10 28 25 32 38 30 61 85 70 60
Binary tree pre-order traversal:
60 30 25 10 28 38 32 70 61 85

Advantages of DFS

  • Depth First Search on a binary tree generally requires less memory than Breadth-First Search
  • Depth-First Search can be easily implemented using recursion

Disadvantages of DFS

  • DFS does not necessarily find the shortest path to a node while Breadth-First Search does

Application of DFS

  • Topological sorting
  • Finding connected components
  • Finding articulation points (cut vertices) of the graph
  • Finding a strongly connected components
  • solving puzzles

Comparing DFS and BFS Algorithms:

The big advantage of DFS is that it has much lower memory requirements than BFS because it’s not required to store all of the children pointers at each level. Depending on the data and what we are looking for, either DFS and BFS can be advantageous. For example in a family tree if we are looking for someone who is still alive and if we assume that person would be at the bottom of the tree then DFS is a better choice. BFS usually takes a very long time to reach that last level.

 The DFS algorithm finds the goal faster. Now if we are looking for a family member who died a very long time ago then the person would be closer to the top of the tree. In this case, BFS finds faster than the DFS. S0 the advantages of either vary depending on the data and what we are looking for. DFS is related to the preorder traversal of a tree. Like preorder traversal, DFS digits each node before its children. The BFS algorithm works similarly to the level order traversal of the trees.

 If someone asks that the DFS is better or BFS is better. The answer depends on the type of problem that they are trying to solve. BFS visits each level one at a time and if we know the solution we are searching for is at low depth then BFS is good. DFS is a better choice if the solution is maximum depth. The below table shows the difference between DFS and BFS in terms of their applications

Applications DFS BFS
Spanning forest, connected components, paths, cycles YES YES
Shortest Paths YES
Minimal use of memory space YES

 

You May Also Like:

Introduction to Graph Data Structure?
Important Types of Graph Data Structure
Breadth-First Search for a Graph Data Structure

That’s all about Depth-First Search or DFS for a Graph Data Structure
If you have any feedback or suggestion please feel free to drop in below comment box.

Leave a Reply

Your email address will not be published.