Does depth first search create redundancy?

Question

I'm trying to make sense of the canonical DFS pseudocode on Wikipedia (http://en.wikipedia.org/wiki/Depth-first_search) -- in particular, the non-recursive implementation that uses a stack.

In BFS, you check whether a node is already explored before pushing it onto the queue, and this guarantees that no node will ever be pushed onto the queue more than once. But in DFS, you only check whether a node is already explored when you pop it off the stack. This seems to be deliberate, as the Wikipedia page says: "[DFS] delays checking whether a vertex has been discovered until the vertex is popped from the stack rather than making this check before pushing the vertex."

But it seems like this delay could cause nodes to be pushed onto the stack more than once. 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.

My question is: why does DFS differ from BFS by delaying the explored check if it creates this redundancy?

Answer 1

I think you have taken the wikipedia algorithm too literally rather than thinking about what it means to visit/discover a node. In BFS also, you can push all the children/adjacent nodes of a node into the queue, but then you have to discard the ones that were already discovered; Same is the case with DFS.

In BFS and DFS, you can choose to:

1. Not push a node that was already discovered. OR
2. Push all adjacent nodes, but discard those nodes while popping, that were already discovered.

The only distinction between BFS and DFS is that, you are pushing on to a stack in BFS vs into a Queue in DFS.