Menu
I have spent lots of time on this issue. However, I can only find solutions with non-recursive methods for a tree: Non recursive for tree, or a recursive method for the graph, Recursive for graph.
And lots of tutorials (I don't provide those links here) don't provide the approaches as well. Or the tutorial is totally incorrect. Please help me.
Updated:
It's really hard to describe:
If I have an undirected graph:
1 / | \ 4 | 2 3 / 1-- 2-- 3 --1 is a cycle.
At the step: 'push the neighbors of the popped vertex into the stack', what's the order in which the vertices should be pushed?
If the pushed order is 2, 4, 3, the vertices in the stack are:
| | |3| |4| |2| _ After popping the nodes, we get the result: 1 -> 3 -> 4 -> 2 instead of 1--> 3 --> 2 -->4.
It's incorrect. What condition should I add to stop this scenario?
334
Iterative Implementation of DFSThe non-recursive implementation of DFS is similar to the non-recursive implementation of BFS but differs from it in two ways: It uses a stack instead of a queue. The DFS should mark discovered only after popping the vertex, not before pushing it.
The only difference between iterative DFS and recursive DFS is that the recursive stack is replaced by a stack of nodes. Algorithm: Created a stack of nodes and visited array.
A DFS without recursion is basically the same as BFS - but use a stack instead of a queue as the data structure.
The thread Iterative DFS vs Recursive DFS and different elements order handles with both approaches and the difference between them (and there is! you will not traverse the nodes in the same order!)
The algorithm for the iterative approach is basically:
DFS(source): s <- new stack visited <- {} // empty set s.push(source) while (s is not empty): current <- s.pop() if (current is in visited): continue visited.add(current) // do something with current for each node v such that (current,v) is an edge: s.push(v) If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
