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 :)
You can try this link: https://cp-algorithms.com/graph/finding-cycle.html (Sorry if this does not help you)
This is the recursive implementation but I'm struggling recreating the same idea iteratively using a stack only.
There may be a more standard way to do this (I never write iterative DFS), but one way is to maintain an array indicating which position in the adjacency list you've reached for each vertex. Then, when we are at a vertex $$$v$$$ and process an edge to a vertex $$$u$$$, add $$$u$$$ to the stack without popping $$$v$$$ and increment the pointer for $$$v$$$. Afterwards, DFS into $$$u$$$, then when we're finished we'll return to $$$v$$$ and process the other edges incident to $$$v$$$. Pop $$$v$$$ from the stack only when you've processed all of its neighbors.
Thank you so much! I never thought of maintaining an array corresponding to the positions. I was able to use a working implementation to solve the original problem my question came from.
Here is the new code for anyone interested. I'm sure it can be cleaned up but this was the best I could do.
....