You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
Current stack-based solution is not exactly equivalent to the recursive one.
When recursive dfs returns from the recursive call, it proceeds immediately to the next vertex in the parent's neighbor list. On the other hand, stack-based version will scan the neighbor list from the beginning each time to find the first white vertex.
I think, this is not guaranteed to be have linear time complexity for any input. As a counter example, consider searching star-like graph from center.
The text was updated successfully, but these errors were encountered:
Yes, I agree with you. The problem asks us to eliminate recursion. To achieve the same time complexity, we have to use a variable to record who's the first WHITE vertex v of a parent u (suppose we are going to explore (u, v)), so that next time we can proceed with the next vertex in the u's neighbor list.
I updated the solution and the C++ code a little bit for better readability.
Link to the solution: https://walkccc.github.io/CLRS/Chap22/22.3/#223-7
Current stack-based solution is not exactly equivalent to the recursive one.
When recursive dfs returns from the recursive call, it proceeds immediately to the next vertex in the parent's neighbor list. On the other hand, stack-based version will scan the neighbor list from the beginning each time to find the first white vertex.
I think, this is not guaranteed to be have linear time complexity for any input. As a counter example, consider searching star-like graph from center.
The text was updated successfully, but these errors were encountered: