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

Автор ARcados, история, 8 лет назад, По-английски

Hi, i'm have problems whit find cicle in D. Subway problem. I have to find a cicle. Initially I thought that by implementing tarjan algorithm I could find the cycle (I tried it and I can't imagine it in an unmanaged graph), but maybe it would be easier to go through it with bfs and store the nodes that I am visiting in a set if they are not in the set . If it means that the nodes of the set are the cycle that I am looking for. Is this correct?. Is there a more efficient way and how can I implement it? Thank you

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

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

Rather than BFS it's simpler to use DFS + set of visited vertices (implement using array of boolean). Try to read this tutorial.