Hi, a warm welcome to tech-maze, in todays article, we are going to explore Breadth first search aka BFS and depth first search aka DFS and how these algorithms help us in multiple ways when we work on Binary Search Tree or Graph.
This article will enhance the understanding of Tree/Graph and its way of functioning in real environment.
Depth first search and breadth first search algorithm has used not only for searching the element, it also used to find the distance between the nodes, find the relationship between the nodes, backtracking, how many level away a node is etc.
While searching the nodes using DFS, we use either user provided stack or JVM stack (in case of recursive method, stack frame used to push/pop to/from JVM stack)
For BFS, we go for Queue in case of graph, but JVM stack used in case of BST.
Lets check how depth first search and breadth first search works in BST and Graph
Binary Search Tree :
Depth First Search (DFS)
In Binary search tree, tree traversal is also knows as DFS, because while traversing through tree we go deep into it starting from the provided node,
this can be achieved in three ways, pre-order, in-order and post-order.
Lets check how we traverse in all three ways
pre-order :-
In pre-order we traverse in this pattern parent-left-right, lets see the code for the same
public void preOrderTraversal(Node root){
if(root!=null){
System.out.println(" Traversing in pre order : "+root.value);
preOrderTraversal(root.left);
preOrderTraversal(root.right);
}
}
in-order :-
In in-order we traverse in left-parent-right pattern, lets see the code for this
public void inOrderTraversal(Node root){
if(root!=null){
inOrderTraversal(root.left);
System.out.println(" Traversing in in order : "+root.value);
inOrderTraversal(root.right);
}
}
post-order :-
In post-order we traverse in left-right-parent pattern, lets see the code for this
public void postOrderTraversal(Node root){
if(root!=null){
postOrderTraversal(root.left);
postOrderTraversal(root.right);
System.out.println(" Traversing in post order : "+root.value);
}
}
Breadth First Search (BFS)
In this process, we start with root and check nodes at each level, breadth here refers to levels, in other words, we can say we go wide instead of deep
lets see how this can be implemented in the code.
//print nodes level wise , it is also called BFS in tree
public int heightoftree(Node root) {
if(root == null)
return 0;
return 1+Math.max(heightoftree(root.left), heightoftree(root.right));
}
public void findLevelNodes(Node root) {
int h = heightoftree(root);
for (int i = 1; i <= h; i++) {
printlevel(root, i);
}
}
public void printlevel(Node root, int h) {
if (root == null)
return;
if(h == 1) {
System.out.println(" the value at each level is : "+root.value);
}else {
printlevel(root.left, h-1);
printlevel(root.right, h-1);
}
}
Logic is quite straight forward, we first get the height (levels) of the tree and then we start traversing through the Nodes at each level.
lets see step by step how control flows
Step 1 :
get the maximum height by traversing and comparing the left sub tree and right sub tree
Step 2 :-
In the method printlevel, we first go to the Node and then check who is the parent of that node and then we print the node value of that level.
Recursive code actually remove boilerplate code but we have to take care of termination logic as well otherwise, while going through the recursive code, it creates lot of stackframe in JVM, and if we miss to provide the termination condition then we will end up out of memory error.
here we have completed DFS and BFS implementation in BST.
Graph :
Lets see how DFS and BFS can be achieved in Graph -----
Depth First Search (DFS)
In the depth first search, we take a stack and whenever we visit any node, we put that in stack, let me show the pictorial representation first and then will go through the logic
//following method is used for depth first search in graph
public void depthFirstSearch(Node node) {
Stack<Node> stk = new Stack<>();
stk.push(node);
while(!stk.isEmpty()) {
Node nd = stk.pop();
if(!nd.visited) {
nd.visited = true;
nd.getSeenList().add(nd);
System.out.println("Not visited ::::: "+nd.data);
}
Set<Node> listnode = nd.getSeenList();
for (Node n : listnode) {
if(n!=null && !n.visited) {
stk.push(n);
}
}
}
}
Logic proceeds in this way :--
Step 1 :
add the node in the stack and then pick this value, check if its visited, if not, then add this node in the set.
Step 2 :
after adding in the set, get its adjacent node list and iterate through it, add in the stack if not visited else skip this
this process will keep on going and at the end of the the loop we will see, we have visited all the nodes, here i am printing the nodes just to show, we have visited each nodes, there may be other requirement to do something with the visited nodes, but the logic would have been same.
Breadth First Search (BFS)
In the breadth first search, we take a queue and whenever we visit any node, we put that in queue, let me show the pictorial representation first and then will go through the logic
here 70 is at first level, 90,60,30,50 at the second level and 10,40,20 at the third level, when we print the items while visiting the nodes, we can see all these items printed together.
//following method is used for breadth first search in graph
public void breadthFirstSearch(Node node) {
Queue<Node> queue = new LinkedList<>();
queue.add(node);
while(!queue.isEmpty()) {
Node nd = queue.poll();
if(!nd.visited) {
nd.visited = true;
}
List<Node> listnode = nd.getSeenList();
for (Node n : listnode) {
if(n!=null && !n.visited) {
queue.add(n);
}
}
}
}
Logic proceeds in this way :--
Step 1 :
add the node in the queue and then pick this value, check if its visited, if not, then add this node in the set.
Step 2 :
after adding in the set, get its adjacent node list and iterate through it, add in the queue if not visited else skip this
this process will keep on going and at the end of the the loop we will see, we have visited all the nodes, here i am printing the nodes just to show, we have visited each nodes, there may be other requirement to do something with the visited nodes, but the logic would have been same.
That's all folks, hope this will help at some extent, for more details and complete code please have a look in the below GitHub project, I will come up with another article shortly.
Git location for the program : https://github.com/rohitmodi07/Programs
A Big thank you for checking out my article, please share your comment/thoughts.
Comentários