Iterative DFS space complexity O(|E|)? Same vertex appears multiple times in stack?

Question

I'm referring to a question already asked on stackoverflow: https://stackoverflow.com/questions/25988965/does-depth-first-search-create-redundancy

However I'm not quite convinced by the answers provided there.

Some iterative DFS implementations that I have seen (such as the one provided by Wikipedia) allow vertices to be pushed onto the stack more than once.

The space complexity would thus be $Θ(|E|)$ in the worst case. (While a recursive implementation of DFS would only require at most $Θ(|V|)$ space.)

Certain implementations check if a vertex has already been discovered before pushing it onto the stack, but this does not affect the space complexity of $Θ(|E|)$ since a vertex is only marked as discovered when it is popped off the stack and not when it is pushed (Thus we are not keeping track of vertices currently in the stack). This only makes sure that vertices which enter and leave the stack are never pushed onto the stack again.

Instead, one would have to mark a vertex before pushing it onto the stack and then check each time before pushing a vertex if it has already been marked (is currently in the stack) in order to avoid multiple occurrences of a same vertex in the stack (As you would do in BFS, where a queue is used instead).

My question is, why would one want to allow multiple occurrences of a same vertex in the stack and why one cannot simply apply the method mentioned above (which is used in BFS) in order to achieve space complexity of $Θ(|V|)$ ?

To illustrate the issue consider this example from the link that I provided:

For example, consider the graph where node 1 points to node 2, which points to node 3, which points to node 4, and so on, up to node 100. Each of these nodes points to node 0. Consider applying the Wikipedia DFS algorithm to this graph, with node 1 as the start state. First, node 0 will be pushed onto the stack. Then node 2 will be pushed. Next, node 2 will be popped off the stack, and since it has not been explored, its children will be pushed onto the stack, (without checking whether they have already been added to the stack!). Node 2's children are node 0 and node 3. Next, node 3 will be expanded, pushing node 0 and node 4 onto the stack. This will continue until the stack is filled with 100 occurrences of node 0.

Answer 1

why would one want to allow multiple occurrences of a same vertex in the stack

For general remarks, I can only guess here since I can't read the minds of others.

A recursive method incurs quite some cost for managing registers and the (call) stack; an explicit stack may be so much faster that, usually, the iterative method is faster even though it's worse on memory.

Saying "usually", keep in mind that your arguments are worst-case considerations. Depending on the graphs you're looking at, the actual behaviour may be very different. When you ask on Stack Overflow, you'll usually get practice-driven trade-offs: use what's faster in your setting.

why one cannot simply apply the method mentioned above (which is used in BFS) in order to achieve space complexity of O(|V|)

Because then you don't have DFS any more! We always want to follow the edge to a node that we discovered last. We have to keep track of the "older" edges with the explicit stack; the call stack remembers them for us by reference, thus saving the memory.

---

If you are very concerned about memory consumption -- which, depending on your inputs, you may have to be! -- there are ways around keeping duplicates in the stack. Here is one idea.

For each node, store in an array not only whether it was already visited/handled, but also its position in the stack (either by pointer or index). If you add a node to the stack and that position is set remove the old stack entry, then push the new one.

Clearly, this keeps the stack at $\leq |V|$ entries. Also, if removing items from the middle of the stack is fast, it does not make the algorithm (much) slower -- the node will have to be removed either way. If not, then a new trade-off appears.