Thanks for sharing! I had come across similar kinds of issues on my annual LeetCode prep and this very clear articulation is very helpful. Props to the author for making this so easy to visualize.
I’m surprised this isn’t a more common and well known issue.
I stumbled upon this issue when trying to convert a recursive DFS to iterative because my recursive DFS was running out of stack space.
The solution produced by this iterative version was wrong, completely different from the recursive implementation.
It’s fascinating how many primitive, basic algorithms are probably implemented incorrectly but work just well enough that no one ever cares or notices… reminds me of how so many text books have an incorrect or overflowing version of binary search.
def dfs(graph, source):
n = len(graph)
visited = set()
stack = [source]
while stack:
node = stack.pop()
if node in visited:
continue
visited.add(node)
for nbr in graph[node]:
stack.append(nbr)
So I don't know what all the confusion is about...
Thanks for sharing! I had come across similar kinds of issues on my annual LeetCode prep and this very clear articulation is very helpful. Props to the author for making this so easy to visualize.
I’m surprised this isn’t a more common and well known issue.
I stumbled upon this issue when trying to convert a recursive DFS to iterative because my recursive DFS was running out of stack space.
The solution produced by this iterative version was wrong, completely different from the recursive implementation.
It’s fascinating how many primitive, basic algorithms are probably implemented incorrectly but work just well enough that no one ever cares or notices… reminds me of how so many text books have an incorrect or overflowing version of binary search.
This is already the standard stack based DFS?
So I don't know what all the confusion is about...