43
$\begingroup$

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.

Improve this question
$\endgroup$
4
  • 5
    $\begingroup$ I have seen students struggle with this, so I don't think it is strictly too simple. However, what more than "Yes" or "No" should an answer contain? The desired granularity is not clear from the question. $\endgroup$
    – Raphael
    Commented Mar 13, 2012 at 18:30
  • 3
    $\begingroup$ "Yes" would come with a convincing argument; "no" would come with a counterexample. But there are better answers than yes/no once you understand what's going on... $\endgroup$
    – rgrig
    Commented Mar 13, 2012 at 18:34
  • 2
    $\begingroup$ @Joe, Dave: please see the ensuing meta discussion $\endgroup$
    – Gilles 'SO- stop being evil'
    Commented Mar 13, 2012 at 22:26
  • 3
    $\begingroup$ It is possible to write pseudo-code so that simply by changing pop to a stack or a queue operation, we get dfs or bfs. It's also easy to write pseudo-code for which it at first appears that this is true, but it isn't. ics.uci.edu//~eppstein/161/960215.html is a relevant reference. $\endgroup$
    – Joe
    Commented Mar 14, 2012 at 8:23

1 Answer 1

Reset to default
27
$\begingroup$

No, this is not the same as a DFS.

Consider the graph

enter image description here

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.

Improve this answer
$\endgroup$
3
  • 5
    $\begingroup$ This assumes that the adjacency lists have some fixed specific order. In mathematics at least, one views them as a set, and a graph has multiple depth-order traversals, depending on how you happen to iterate the children. (Imagine using hashes for children.) In that sense, ABECD is still a depth-first order. The questioner wonders whether there is a counter-example even in this setting. (Indeed, this is where it starts to get tricky.) $\endgroup$
    – rgrig
    Commented Mar 13, 2012 at 22:58
  • 3
    $\begingroup$ @rgrig: Well, this is one of the possible traversals, and that leads to a sequence which is not in DFS. No matter how you iterate, marking $D$ as seen will result in the DFS 'below' $E$ to come out wrong, if you don't visit $D$ first. $\endgroup$
    – Aryabhata
    Commented Mar 13, 2012 at 23:03
  • 1
    $\begingroup$ @Arybhata: Oh, sorry, I don't know why I was assuming that you meant for the edges to be directed and pointing downward. Their are undirected, so you are right: This is a counterexample even for what I was saying in the comment. (This is weird: I had to misspell your handle, so it doesn't get removed by SE.) $\endgroup$
    – rgrig
    Commented Mar 13, 2012 at 23:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.