5
$\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$
2
  • 1
    $\begingroup$ This strikes me as a quite broad question. Community votes, please! $\endgroup$
    – Raphael
    May 17, 2016 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, 2016 at 9:53

2 Answers 2

0
$\begingroup$

Shortest cycle: BFS has the nice property that, if started from u, the first time the BFS finds u is when the shortest cycle that includes u has been completed.

Email infections: Determining whether a computer is infected from looking at the email metadata, BFS and DFS are about the same, since you don't know if that worker was infected early, late, or not at all. The trick in that problem is to set up the graph right so a search can be done with as few conditionals as possible.

$\endgroup$
-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
  • 1
    $\begingroup$ This can't possibly be the whole truth. $\endgroup$
    – Raphael
    Jun 16, 2016 at 13:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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