2. Depth First Search

• • Depth First Search (DFS) is a recursive algorithm for traversing a tree or graph data structure.
• • The process of Depth First Search (DFS) algorithm is Similar to Breadth First Search (BFS).
• • It is called Depth First Search because it traverses from the root node and follows each path up to its greatest depth before moving to the next path. That means when it starts traversing from the root node and choose one successor node and go to the depth of that path i.e., complete all the levels of that path before moving to the next successor node.
• • Depth First Search (DFS) uses the stack data structure for its implementation.

Advantages

• • Depth First Search (DFS) requires very less memory as it only needs to store a stack of the nodes on the path from root node to current node.
• • If it traverses in the right path then it Requires less time to reach the goal node than BFS algorithm.

Disadvantages

• • There is the possibility that many state will reoccur and while goes deep down for searching sometimes it may go to the infinite loop and there is no guarantee of finding the solution.

Time Complexity

Time complexity of DFS will be equivalent to the node traversed by the algorithm. It is given by: , Where, m= maximum depth of any node and this can be much larger than d (Shallowest solution depth).
T(n)=1+n²+n³+....+nⁿ=O(n^m)

Space Complexity

DFS algorithm needs to store only single path from the root node, hence space complexity of DFS is equivalent to the size of the fringe set, which is O(bm).

Completeness

DFS search algorithm is complete within finite state space as it will expand every node within a limited search tree.

Optimality

DFS search algorithm is non-optimal, as it may generate a large number of steps or high cost to reach to the goal node.

About the Author

Silan Software is one of the India's leading provider of offline & online training for Java, Python, AI (Machine Learning, Deep Learning), Data Science, Software Development & many more emerging Technologies.

We provide Academic Training || Industrial Training || Corporate Training || Internship || Java || Python || AI using Python || Data Science etc