1

I am confused about this answer. Why can't DFS decide if there is a cycle in a directed graph while visiting each node and each edge at most once? Using the white, gray, black method, one should be able to find a cycle if there is a backward edge.

For an unconnected directed graph, why can't one do the following: run DFS from an arbitrary node v and visit as many nodes as v is connected to, then run DFS on another unvisited arbitrary node in the graph, if any, until all nodes are visited?

It seems to me that DFS should be able to find a cycle if it exists in at most o(|V|+|E|) time. Is this claim in the above mentioned answer wrong?

"It is possible to visit a node multiple times in a DFS without a cycle existing"

Moreover, as this other answer suggest, if a cycle exists, DFS should find it after exploring a maximum of |V| edges, so the run time is really O(|V|).

What am I missing?

Update and conclusions:

Based on Pham Trung's comments, it looks like the "simple DFS" in that answer refers to a DFS starting from one node in a strongly connected graph. As I understand it, for a general case that the graph might be unconnected, the following statements should be true:

  • Using DFS and starting from an arbitrary unvisited node in an unconnected graph, it is true that each node might be visited more than once, but using white-gray-black coloring, a cycle -if exists - will be correctly found.
  • The run time of such a DFS algorithm is O(d.|V|+|E|), where d is the max in-degree among all nodes (i.e. the max time that we can visit each node using such DFS-based algorithm)
  • Moreover, as this other answer suggest, if after exploring O(|V|) edges, a cycle was not found, it does not exist. So the runtime is really O(|V|).
Community
  • 1
  • 1
Ari
  • 7,251
  • 11
  • 40
  • 70

1 Answers1

2

Imagine we have this simple graph with these edges:

  • 1 -> 3

  • 2 -> 3

    1 ----->3
        ^
        |
2--------

So, in our first dfs, we discover node 1 and 3. And, we continue to do dfs with node 2, now, we encounter node 3 again, but is this a cycle? obviously not.

One more example:

  • 1 -> 3

  • 1 -> 2

  • 2 -> 3

    1----->3
|      ^
|      |
|      |
v      |
2-------

So, starting with node 1, we visit node 3, back to node 2, and now, we encounter node 3 one more time, and, this case, it is not a cycle also.

As far as I understand the simple depth-first-search from Jay Conrod's answer means, a normal, original DFS (only checking for connected component). In the same answer, he also described how to modify simple DFS to find the existence of cycle, which is exactly the algorithm OP has cited. And right below, another answer also mentioned a lemma in the famous Introduction to algorithm book

A directed graph G is acyclic if and only if a depth-first search of G yields no back edges

In short, OP's understanding to detect cycle in directed graph is correct, it is just some complexities and shortcuts have lead to misunderstanding.

Pham Trung
  • 11,204
  • 2
  • 24
  • 43
  • DFS algorithm with white, gray, and black colors for nodes only declares an edge to be a backedge when the color is gray (i.e. that node's descendants is being visited) Once all decendants are visited it will be turned into black color. In your first example, after visiting node 3, its color will be set to black, and when you get to 3 from 2 again because it is not gray, no cycle will be declared. Same thing for your second example. So the algorithm works correctly. – Ari Jun 02 '16 at 16:37
  • @Ari Actually, as far as I understand `a simple depth-first-search is not good enough to find a cycle` from Jay Conrod's answer which means, a normal DFS (only checking for connected component). But, in the same answer, he also described how to modify `simple DFS` to find the existence of cycle, which is exactly the algorithm you have cited. And right below, another answer also mentioned a lemma in the famous Introduction to algorithm book `A directed graph G is acyclic if and only if a depth-first search of G yields no back edges` – Pham Trung Jun 02 '16 at 17:00
  • @Ari I think it is because he didn't clearly define what can be considered `simple DFS` that causing your confusion. – Pham Trung Jun 02 '16 at 17:03
  • Thanks, I think you are right. I updated my question. I appreciate if you can confirm my conclusions. – Ari Jun 02 '16 at 17:48