Блог пользователя old._.monk

Why cycle detection algorithm differs in directed and undirected graphs?
Автор old._.monk, история, 3 года назад, По-английски

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?

  • Проголосовать: нравится
  • +1
  • Проголосовать: не нравится

»
3 года назад, # |
  Проголосовать: нравится +12 Проголосовать: не нравится

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$$$.

→ Ответить