CODEWITHSUNDEEP
algorithmgraphcomputer-sciencedirected-graph
Ari
Ari

Reputation: 7556

Confusions on finding a cycle in a possibly unconnected directed graph

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:

Upvotes: 1

Views: 659

Answers (1)

Pham Trung
Pham Trung

Reputation: 11284

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.

Upvotes: 2

Related Questions