Why DFS and not BFS for finding cycle in graphs

Question

Predominantly DFS is used to find a cycle in graphs and not BFS. Any reasons? Both can find if a node has already been visited while traversing the tree/graph.

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.

View more solutions

Comments

[Amber]

(Memory efficient because you get to backtrack sooner, and easier to implement because you can just let the stack take care of storing the open list instead of having to explicitly maintain it.)

[Hank Gay]

IMO, it's only easier if you can rely on tail recursion.

[IVlad]

A lot of magic numbers there. I disagree with the "DFS is faster" arguments. It depends entirely on the input, and no input is more common than another in this case.

[Rex Kerr]

@Vlad - The numbers aren't magic. They are means, are are stated as such, and are almost trivial to calculate given the assumptions I stated. If approximating by the mean is a bad approximation, that would be a valid criticism. (And I explicitly stated that if you could make assumptions about the structure, the answer could change.)

[IVlad]

the numbers are magical because they don't mean anything. You took a case DFS does better on and extrapolated those results to the general case. Your statements are unfounded: "DFS will tend to hit the cycle when it's covered about half the tree": prove it. Not to mention that you cannot talk about cycles in a tree. A tree does not have a cycle by definition. I just don't see what your point is. DFS will go one way until it hits a dead end, so you have no way of knowing how much of the GRAPH (NOT tree) it will explore on average. You just picked a random case that proves nothing.

[Dimitris Andreou]

"unmark them as you backtrack" - at your own peril! This can easily lead to O(n^2) behavior, specifically such a DFS would misunderstand cross edges as "tree" edges ("tree" edges would also be a misnomer since they wouldn't actually form a tree anymore)

[Mark Byers]

@Dimitris Andreo: You can use three visited states instead of two to improve performance. With directed graphs there's a difference between 'I've seen this node before' and 'This node is part of a loop'. With undirected graphs they are equivalent.

[Dimitris Andreou]

Exactly, you definitely need a third state (to make the algorithm linear), so you should consider revising that part.

[Rex Kerr]

@Vlad - All noncyclic fully connected undirected graphs are (unrooted undirected) trees. I meant "a graph that would be a tree save for one spurious link". Perhaps this isn't the main application for the algorithm--maybe you want to find cycles in some tangled graph that has very many links that make it not a tree. But if it is tree-like, averaged over all graphs, any node is equally likely to be the source of said spurious link, which makes the expected tree coverage 50% when the link is hit. So I accept that the example may not have been representative. But the math should be trivial.

[brain storm]

@MarkByers: I have posted a question in this link based on your answer here. can you comment on this plz: stackoverflow.com/questions/20555291/…

[brain storm]

@DimitrisAndreou: I have posted a question where I do not use backtracking nor a third state is essential, but could detect cycles in directed graph. can you pass you valuable comment here: stackoverflow.com/questions/20555291/…

[smasher]

Can you explain how DFS will clearly identify that cycle does not exist in your example.I agree that the cycle does not exist in provided example.But if we go from A->B and then A->C->B we will find that B was already visited and its parent is A not C..and i read that DFS will detect the cycle by comparing the parent of already visited element with current node from which direction we are checking at this moment.am i getting DFS wrong or what?

[Prune]

All you've shown here is that this particular implementation doesn't work, not that it's impossible with BFS. In fact, it is possible, although it takes more work and space.

[Aditya Raman]

@Prune: All the threads(i think) here are trying to prove that bfs wont work for detecting cycles. If you know how to counter prove you should give the proof. Simply saying that efforts are greater wont suffice

[Prune]

Since the algorithm is given in the linked postings, I don't feel it's appropriate to repeat the outline here.

[Aditya Raman]

I couldnt find any linked postings, hence asked for the same. I agree with your point about bfs capability and have just thought about the implementation. Thanks for the tip :)

[plasmacel]

Indeed, this is the most (maybe the only) related answer here, elaborating on the actual reasons.

[mahee96]

BFS can work for cycle detection in Directed graph too, Look for Kahn's algorithm which uses DAG facts to detect cycle 1. In DAG there must be atleast 1 root(indeg=0) 2. After each predecessor node is processed, there must be atleast 1 new root node. This is done be reducing indegree of direct successor nodes at each root node starting from topmost root node(indeg=0). More info: geeksforgeeks.org/detect-cycle-in-a-directed-graph-using-bfs