Depth First Search (DFS) - Algorithm - Graph Traversal

"What is Depth First Search (DFS)"
  • DFS is an algorithm for traversing the Graph Data Structure. 
  • We can start from a node and go to one of its neighbours and then its neighbour and so on. After this, we come to the other neighbour of the start node and check its neighbour and so on. Basically, we are traversing in depth.
  • It is similar to the Depth First Traversal of a tree, but unlike a tree, a graph may contain cycles, so we need to keep track of visited nodes too in order to ensure we do not traverse the already traversed node and thus avoid getting stuck in the cycle or loop forever.

Algorithm for DFS : [Time Complexity: O(V+E) ,  Space Complexity: O(V+E)]

If you want to do DFS recursively :

1. For each node in the node list which are not visited call dfs(current node, visited hashset):
        2. If current node is present in visited hashset return 
        3. Else Print current node and add current node to visited hashset
        4. For every adjacent node of current node :
                5. if current adjacent node is not in visited hashset, call dfs(current adjacent node, visited hashset) recursively.


If you want to do DFS iteratively :

1. For each node in the node list which are not visited call dfs(current node, visited hashset):
    2. Add current node to stack
    3. While stack is not empty:
            4. pop from stack and print current node
            5. Add current popped node in visited Hashset
            6. for all adjacent node of current node :
                   7. if current adjacent node is not in visited HashSet, then add it to stack and also add it to the visited hashset .
     


The implementation DFS traversal for all 6 types of graphs is exactly the same.

"BFS VS DFS - When To Use Which Method ?"
  • BFS is optimal for finding the shortest distance as compared to  DFS. To explain this let's take an example of a graph:
     In the above graph, suppose we want to find the shortest distance between node 1 and 3 and 1 being the start node. Suppose we use DFS. We start from node1 and suppose we go to node 2 first. By doing that you can see we follow this path: 1->2->4->6->5->3. Node 3 is found very late. But if we use BFS in this case, we follow the path : 1->2->3. Clearly, BFS wins the game of finding the shortest distance quickly than DFS. 


 

Comments

Post a Comment

Popular posts from this blog

Binary Heap - Introduction

Image
#Image Credit - GeeksForGeeks Types of heap: Min Heap - every node is less than or equal to  its children(s) Max Heap - every node is more than or equal to its children(s) Operations on any heap : create insert extract/delete - we can extract/delete only the top node in any heap traverse delete entire heap get size of heap peek top of heap We should prefer implementing binary heap using arrays and not linked list, as during bottom to top heapify, in reaching the bottom rightmost node we take only 0(1) time in case of array but we take 0(n) time in case of linked list because first, we need to level order traverse the binary heap tree to get bottom-most rightmost element.  Heaps are used to efficiently implement:  Prim's Algorithm Heapsort Priority queue
Read more

Divide and Conquer - Introduction

Image
What is Divide and Conquer? Divide and Conquer is an algorithm paradigm in which we break down a given problem into smaller sub-problems of similar type until the sub-problems are small enough to be solved directly. The solution to these sub-problems are then combined to give a solution to the original problem.  Study the diagram below, it will then make more sense about what we do in Divide and Conquer : Where to Apply Divide and Conquer? The Divide and Conquer can be applied to all those problems that show Optimal Substructure property.  So, What is this Optimal Substructure property now? If we can break down a problem into similar sub-problems and the solution of these sub-problems can be used to create the solution of the whole problem, then that problem is said to have the Optimal Substructure property. For eg. : Fibonacci(n) = Fibonacci(n-1) + Fibonacci(n-2),    In this example, we can see that if we want to find the Fibonacci number at the nth place, we can br...
Read more

Bubble Sort

Time complexity - O(n^2)  || Space Complexity - O(1) Bubble sort is an inplace sorting algorithm, that means we do not any extra space while bubble sorting public class Main {     public static void main(String[] args) throws Exception {         int[] arr={1,4,4,5,6,2,3,90,120,43,0};                  System.out.println("UnSorted Array :");         for(int i=0;i<arr.length;i++){             System.out.print(arr[i]+" ");         }         System.out.println();         // bubble sort         for(int i=0;i<arr.length-1;i++){ // iterates through first to last cell             for(int j=0;j<arr.length-1-i;j++){ // inner loop controls swapping and extent to which swapping is to be performed in array     ...
Read more