Iterative DFS with stack-based graph traversal (2024)
1–10 of 10 posts
Re: Iterative DFS with stack-based graph traversal (2024)
#2Thanks 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.
Re: Iterative DFS with stack-based graph traversal (2024)
#3I’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.
Re: Iterative DFS with stack-based graph traversal (2024)
#4This is already the standard stack based DFS?
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)
Re: Iterative DFS with stack-based graph traversal (2024)
#5I implemented an iterative, stack-based DFS iterator in JS last year for a project that I didn't end up using it on. Maybe someone else can find some use of it: https://gist.github.com/nothingnesses/5f974a43a2da5d1d8a6b9c...
Re: Iterative DFS with stack-based graph traversal (2024)
#6I’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 wel…
reminds me of how so many text books have an incorrect or overflowing version of binary search.
Extra, Extra - Read All About It: Nearly All Binary Searches and Mergesorts are Broken https://research.google/blog/extra-extra-read-all-about-it-n...
Re: Iterative DFS with stack-based graph traversal (2024)
#7I’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 wel…
Why would it be a common issue?
People usually implement graph traversal first and only after that do they choose a FIFO queue for BFS or a stack for DFS as their data structure.
Re: Iterative DFS with stack-based graph traversal (2024)
#8So... am I misunderstanding or is it enough to swap the iteration over the neighbours of a node and the visited check?
for nbr in graph[node]:
if not visited[nbr]:
if node in visited: continue
visited.add(node)
for nbr in graph[node]:
stack.append(nbr)Re: Iterative DFS with stack-based graph traversal (2024)
#9So... am I misunderstanding or is it enough to swap the iteration over the neighbours of a node and the visited check? for nbr in graph[node]: if not visited[nbr]: into if node in visited: continue visited.add(node) for nbr in graph[node]: stack.append(nbr)
It should be enough :)
Re: Iterative DFS with stack-based graph traversal (2024)
#10One thing to keep in mind (which the original cited article in this article gets right, but this article gets wrong) - there is no guarnateed unique ordering of children visitation for nodes with >1 child. The parts they copy from the original article talk about this correctly, the parts they didn't, don't :)
The DFS orderings where the children visitation is swapped, etc, are all still equally correct and valid. That is - a DFS algorithm that randomized the children order is still valid.
IE for example, if you change the "for nbr in graph[node]" line to "for nbr in reversed(sorted(graph[node]))", the resulting DFS ordering is still valid and correct.
If you want them in a specific ordering, you'd usually have to force them into it in the algorithm. It rarely makes sense to try to force the structure to be ordered (as they do here) for the algorithm.
This often hits people who use graphs with pointers, or multiple threads, or ...