Qué se obtiene DFS si cambia la cola a una pila en una aplicación BFS?

Question

Aquí está el pseudocódigo estándar para la búsqueda en anchura:

{ 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

Aquí push y pop se supone que son operaciones de la cola. Pero lo que si son operaciones de pila? Hace los vértices visita algoritmo resultante con el fin de primero en profundidad?

---

Si usted votó por el comentario "este es trivial", me gustaría pedir que explique por qué es trivial. Me parece que el problema bastante complicado.

Answer 1

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.