Return to 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 $O(|E|)$ in the worst case. (While a recursive implementation of DFS would only require at most $O(|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 $O(|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 $O(|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.

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.

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 $O(|E|)$ in the worst case. (While a recursive implementation of DFS would only require at most $O(|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 $O(|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 have 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 $O(|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.

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 $O(|E|)$ in the worst case. (While a recursive implementation of DFS would only require at most $O(|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 $O(|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 $O(|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.