Do you get DFS if you change the queue to a stack in a BFS implementation?

Answered By : Aryabhata

No, this is not the same as a DFS.

Consider the graph

If you push the nodes in right to left order, the algorithm gives you a traversal:

$A, B , E, C , D$

while a DFS would expect it to be

$A,B,E,D,C$

The problem occurs because you mark it as seen at the time of pushing, rather than at the time of visiting. As pointed out in the comments, if you mark at the time of visiting, your space requirements might go up to $\Theta(V+E)$ rather than $\mathcal{O}(V)$.

I agree, the problem is not trivial.

Problem Detail: 

Here is the standard pseudocode for breadth first search:

{ seen(x) is false for all x at this point } push(q, x0) seen(x0) := true while (!empty(q))   x := pop(q)   visit(x)   for each y reachable from x by one edge     if not seen(y)       push(q, y)       seen(y) := true 

Here push and pop are assumed to be queue operations. But what if they are stack operations? Does the resulting algorithm visit vertices in depth-first order?

---

If you voted for the comment "this is trivial", I'd ask you to explain why it is trivial. I find the problem quite tricky.

Asked By : rgrig

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/329