How can I find the start of a cycle in a graph iteratively

Revision en1, by Onitap, 2023-09-23 21:53:23

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

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English Onitap 2023-09-23 21:53:23 1582 Initial revision (published)