22.3-7 Stack-based DFS time complexity

[i-to]

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.

[walkccc]

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.

Thanks.