4
$\begingroup$

Preparing for an interview.

I see two cases where each one is specially suited

BFS: When you need to find shortest path between vertices (if one exists).

DFS: If you need to find cycles in a directed graph:

Uses-case where both can be used: Finding cycle in undirected graph, Is there a path from one vertex to another

Are there any other specialized or common cases?

In general DFS is considered to be simpler (though if graph is very deep, I am assuming we can have a stack overflow due to excessive recursion). So, if both can be used for a use-case, use DFS?

$\endgroup$
  • 1
    $\begingroup$ This strikes me as a quite broad question. Community votes, please! $\endgroup$ – Raphael May 17 '16 at 9:52
  • 1
    $\begingroup$ "though if graph is very deep, I am assuming we can have a stack overflow due to excessive recursion" -- if the maximum out-degree is large, the queue can overflow memory in BFS as well. Also, you can easily implement DFS iteratively using an explicit stack which may be more memory-efficient. $\endgroup$ – Raphael May 17 '16 at 9:53
-2
$\begingroup$

Bfs and Dfs both are good state space search algorithms. If search space is infinite then its good to use Bfs because dfs can be lost in infinite space and will not return any result. Also, Bfs searches result in neighbors and then go neighbor by neighbor on other hand dfs searches for answer branch by branch. If you search key is near starting point then go for bfs

$\endgroup$
  • 1
    $\begingroup$ This can't possibly be the whole truth. $\endgroup$ – Raphael Jun 16 '16 at 13:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.