When to use DFS and when use BFS?

Question

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?

Answer 1

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.

Answer 2

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