0
$\begingroup$

Let consider a connected graph $G = (V, E)$ which is not oriented. One way to detect a cycle in such a graph is :

  1. Create an array : seen of size $\mid V \mid$ with seen[i] = false for all $i$

  2. Perform a DFS (or BFS) starting at the node $0$.

  3. When we see a node $i$ : we have two cases : if seen[i] = false then seen[i] = true else we found a cycle.

One idea to prove the correction of this algorithm is saying the following : if the algorithm return true it means there two nodes $x$ and $y$ such that when we looked at $y$ we have : seen[y] = false and seen[x] = true thus there is a cycle namely the cycle which begin at $x$ and use the only path that connect $x$ and $y$ in the DFS tree and then use the edge $(y,x)$.

The problem is that this is not really rigourous and I am really lokking for an invariant that we help me do the correction of this algorithm rigourously. So is there any invariant I can use here ?

Thank you very much !

$\endgroup$
0
$\begingroup$

Assuming we execute line 3 when you first visit a node, and assuming you are working with directed graphs, this algorithm is incorrect (consider what happens with a cross edge discovered by DFS).

Alternatively, assuming you are working with undirected graphs:

The missing part of your argument is the "thus" part; why does the existence of two such nodes imply the existence of a cycle?

To work out the proof, I suggest categorizing what types of edges can exist in the search tree for an undirected graph: tree edges? forward edges? back edges/ cross edges? Then, categorize what type of edge caused you to visit x when seen[x] was true. What does that mean the search tree has to look like?

$\endgroup$
  • $\begingroup$ Yes I am working with undirected graph. Actually I understand how the algorithm work (intuitively) but I am not able to find a correct invariant that will help me do the correction. $\endgroup$ – 1597846254899 Mar 31 at 17:19
  • $\begingroup$ @1597846254899, yes, and I am giving you guidance on that will hopefully help you work out a proof of correctness, if you spend some time thinking about it. I suggest you spend some time working through the details in the last paragraph of my answer, and make sure you can answer all of the questions I listed in the last paragraph of my answer. $\endgroup$ – D.W. Mar 31 at 17:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.