Onitap's blog

By Onitap, history, 5 months ago, In English

Given that a graph has a cycle, I would like to perform a dfs on a starting node and find the first node in its path which is the start of the cycle. After we perform dfs, the first node we find that has already been visited but is not the parent of the current node would indicate we have a cycle. Since it is the first node we found that satisfies this, it is the start of our cycle. This can be coded easily using recursion but I prefer the iterative dfs implementation.

The main problem I did not know how to solve was when a node has neighbors and we explore down one of its paths. When we pop back and iterate over the rest of its neighbors, how do we start where we left off and not the beginning of its neighbors again.

Here is my code in progess. Thank you for reading and any help is appreciated :)

Spoiler

Full text and comments »

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