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

Автор Onitap, история, 14 месяцев назад, По-английски

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
  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
14 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

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.

»
14 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

....