ARcados's blog

By ARcados, history, 8 years ago, In English

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

  • Vote: I like it
  • 0
  • Vote: I do not like it

| Write comment?
»
8 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

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