Disadvantages of Depth First Search

Applications of Depth First Search:

1. Detecting cycle in a graph: A graph has a cycle if and only if we see a back edge during DFS. So we can run DFS for the graph and check for back edges....

Advantages of Depth First Search:

Memory requirement is only linear with respect to the search graph. This is in contrast with breadth-first search which requires more space. The reason is that the algorithm only needs to store a stack of nodes on the path from the root to the current node. The time complexity of a depth-first Search to depth d and branching factor b (the number of children at each node, the outdegree) is O(bd) since it generates the same set of nodes as breadth-first search, but simply in a different order. Thus practically depth-first search is time-limited rather than space-limited.  If depth-first search finds solution without exploring much in a path then the time and space it takes will be very less. DFS requires less memory since only the nodes on the current path are stored. By chance DFS may find a solution without examining much of the search space at all....

Disadvantages of Depth First Search:

The disadvantage of Depth-First Search is that there is a possibility that it may down the left-most path forever. Even a finite graph can generate an infinite solution to this problem is to impose a cutoff depth on the search. Although ideal cutoff is the solution depth d and this value is rarely known in advance of actually solving the problem. If the chosen cutoff depth is less than d, the algorithm will fail to find a solution, whereas if the cutoff depth is greater than d, a large price is paid in execution time, and the first solution found may not be an optimal one.  Depth-First Search is not guaranteed to find the solution.  And there is no guarantee to find a minimal solution, if more than one solution....