I have seen several variants of DFS algorithms used to check existence of cycles in graphs.
They all have the same structure : do a DFS in the graph. There is a cycle in the graph if and only if there exists a node which, while being treated, has a neighbour which has property P.
The variants are based on different properties used for P :
- P = already visited but not the current node's parent
- P = "grey" (a node already discovered but not all its children are already visited) but not the current node's parent
- P = a node currently in the stack. By stack, here I mean the basic stack that is used to implement the DFS, nothing more.
I've seen 1. and 2. a lot of times here and in the literature. For 3., I wrote it myself, I have a proof of the equivalence with the existence of a cycle, that I am quite confident in (but I could be wrong !)
My question is : are these three equivalent (to the existence of a cycle, in other words are those correct) ? Under some specific assumptions for some of them ?
What I already think I know :
- I know that the variant 1. does not work for directed graphs (because the already visited neighbour might not be reachable in this direction). In undirected graphs it seems that all the three variants are equivalent (to the existence of a cycle).
- If 2. and 3. are correct they are of course equivalent since both are equivalent to the existence of a cycle. But is there a simple way to see their equivalence directly ? Clearly 3 implies 2 since a node in the stack is gray. But how is it true that if there is a node with a gray neighbour, then there is a node with a neighbour in the stack ?
- It seems to me that the difference between grey nodes as in 2. and stack nodes is that grey nodes are "recursive stack" nodes (i.e. nodes in the stack of the recursive calls if DFS is implemented recursively)
