any advantages of using BFS over DFS for finding cycles in directed graph

Question

This is an interview question.

In a directed graph how can you find a cycle? is it possible to find using BFS, why BFS is preferred over DFS.

AFAIK, DFS is a clear winner in this case, as it's easy to find the cycle and it's more efficient in terms of memory. So are there any advantages of using BFS in this case, that I am unaware of.

Answer 1

When doing BFS, you will find the cycle while developing only O(B^d) nodes, where B is the branch factor and d is the size of the cycle + header from the source to it. (the length of the cycle if the source of the BFS is in the cycle).

DFS cannot guarantee you this, and might discover the entire graph before finding the cycle.

Answer 2

The answer to using which algorithm to find a solution is often "it depends".

What kind of graph is it? Statistically where do cycles occur? If a graph is very deep, and cycles tend to happen in the shallow parts, then BFS is obviously preferable.

Memory usage of BFS can be mitigated by using iterative deepening.

Answer 3

In Directed graph, a cycle is present if and only if a back edge exists. A backedge is an edge pointing to itself or pointing to its ancestors

Why DFS and not BFS for finding cycle in graphs