Why DFS and not BFS for finding cycle in graphs

Solution 1:

Depth first search is more memory efficient than breadth first search as you can backtrack sooner. It is also easier to implement if you use the call stack but this relies on the longest path not overflowing the stack.

Also if your graph is directed then you have to not just remember if you have visited a node or not, but also how you got there. Otherwise you might think you have found a cycle but in reality all you have is two separate paths A->B but that doesn't mean there is a path B->A. For example,

If you do BFS starting from 0, it will detect as cycle is present but actually there is no cycle.

With a depth first search you can mark nodes as visited as you descend and unmark them as you backtrack. See comments for a performance improvement on this algorithm.

For the best algorithm for detecting cycles in a directed graph you could look at Tarjan's algorithm.

Solution 2:

1. DFS is easier to implement
2. Once DFS finds a cycle, the stack will contain the nodes forming the cycle. The same is not true for BFS, so you need to do extra work if you want to also print the found cycle. This makes DFS a lot more convenient.

Solution 3:

A BFS could be reasonable if the graph is undirected (be my guest at showing an efficient algorithm using BFS that would report the cycles in a directed graph!), where each "cross edge" defines a cycle. If the cross edge is {v1, v2}, and the root (in the BFS tree) that contains those nodes is r, then the cycle is r ~ v1 - v2 ~ r (~ is a path, - a single edge), which can be reported almost as easily as in DFS.

The only reason to use a BFS would be if you know your (undirected) graph is going to have long paths and small path cover (in other words, deep and narrow). In that case, BFS would require proportionally less memory for its queue than DFS' stack (both still linear of course).

In all other cases, DFS is clearly the winner. It works on both directed and undirected graphs, and it is trivial to report the cycles - just concat any back edge to the path from the ancestor to the descendant, and you get the cycle. All in all, much better and practical than BFS for this problem.

Solution 4:

I don't know why such an old question popped up in my feed, but all the previous answers are bad, so...

DFS is used to find cycles in directed graphs, because it works.

In a DFS, every vertex is "visited", where visiting a vertex means:

1. The vertex is started

2. The subgraph reachable from that vertex is visited. This includes tracing all untraced edges that are reachable from that vertex, and visiting all reachable unvisited vertexes.

3. The vertex is finished.

The critical feature is that all edges reachable from a vertex are traced before the vertex is finished. This is a feature of DFS, but not BFS. In fact this is the definition of DFS.

Because of this feature, we know that when the first vertex in a cycle is started:

1. None of the edges in the cycle have been traced. We know this, because you can only get to them from another vertex in the cycle, and we're talking about the first vertex to be started.
2. All untraced edges reachable from that vertex will be traced before it is finished, and that includes all the edges in the cycle, because none of them has been traced yet. Therefore, if there is a cycle, we will find an edge back to the first vertex after it is started, but before it is finished; and
3. Since all edges that are traced are reachable from every started-but-unfinished vertex, finding an edge to such a vertex always indicates a cycle.

So, if there is a cycle, then we are guaranteed to find an edge to a started-but-unfinished vertex (2), and if we find such an edge, then we are guaranteed that there is a cycle (3).

That's why DFS is used to find cycles in directed graphs.

BFS provides no such guarantees, so it just doesn't work. (notwithstanding perfectly good cycle-finding algorithms that include BFS or similar as a sub-procedure)

An undirected graph, on the other hand, has a cycle whenever there are two paths between any pair of vertexes, i.e., when it's not a tree. This is easy to detect during either BFS or DFS -- The edges traced to new vertexes form a tree, and any other edge indicates a cycle.

Solution 5:

BFS wont work for a directed graph in finding cycles. Consider A->B and A->C->B as paths from A to B in a graph. BFS will say that after going along one of the path that B is visited. When continuing to travel the next path it will say that marked node B has been again found,hence, a cycle is there. Clearly there is no cycle here.