Блог пользователя kittyK

Cycles
Автор kittyK, история, 4 года назад, По-английски

It might be silly question for pro coders. It is very basic question .I actually googled but could not understand well.

So the question is why the way of finding cycle is different for directed and undirected graph ?

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

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

In undirected graph, you have to keep track of parent node also. Example given an undirected graph as:

2 1

1 2

if you apply directed graph cycle check method then it would give you a cycle (1-2-1) which is not the case

→ Ответить
»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

There are more than one ways to find cycles and they don't have to be different for the two types of graphs. For example, DFS will work for both.

→ Ответить