old._.monk's blog

Why cycle detection algorithm differs in directed and undirected graphs?
By old._.monk, history, 3 years ago, In English

I'm not able to grasp why the algorithms for cycle detection differ when graphs are directed or undirected.

I found the two algorithms here cp algorithms link

Found an explanation on stackoverflow, but it's still unclear.

Is there any counter-example?

  • Vote: I like it
  • +1
  • Vote: I do not like it

Comments Comments (1)
| Write comment?
»
3 years ago, # |
  Vote: I like it +12 Vote: I do not like it

Because having a cycle in a directed and an undirected graph isn't the same thing.

Suppose you have a 2-vertex undirected graph represented with the following adjacency list:

  • neighbors[0] = {1}
  • neighbors[1] = {0}

This graph doesn't have a cycle. It's just an edge.

Now interpret the same adjacency list as a directed graph. Now there is a cycle $$$0 \to 1 \to 0$$$.

→ Reply