¿Obtiene DFS si cambia la cola a una pila en una implementación de BFS?

35

Aquí está el pseudocódigo estándar para la primera búsqueda de amplitud:

{ 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í pushy popse supone que son operaciones de cola. Pero, ¿y si son operaciones de pila? ¿El algoritmo resultante visita los vértices en primer orden de profundidad?


Si votó por el comentario "esto es trivial", le pido que explique por qué es trivial. El problema me parece bastante complicado.

rgrig
fuente
55
He visto a estudiantes luchar con esto, así que no creo que sea estrictamente demasiado simple. Sin embargo, ¿qué más que "Sí" o "No" debe contener una respuesta? La granularidad deseada no está clara a partir de la pregunta.
Raphael
2
"Sí" vendría con un argumento convincente; "no" vendría con un contraejemplo. Pero hay mejores respuestas que sí / no una vez que entiendes lo que está pasando ...
rgrig
2
@ Joe, Dave: por favor vea la meta discusión que sigue
Gilles 'SO- deja de ser malvado'
3
Es posible escribir un pseudocódigo para que simplemente cambiando popa una operación de pila o de cola, obtengamos dfs o bfs. También es fácil escribir pseudocódigo para el que al principio parece que esto es cierto, pero no lo es. ics.uci.edu//~eppstein/161/960215.html es una referencia relevante.
Joe

Respuestas:

23

No, esto no es lo mismo que un DFS.

Considera la gráfica

ingrese la descripción de la imagen aquí

Si empuja los nodos en orden de derecha a izquierda, el algoritmo le ofrece un recorrido:

UNA,si,mi,do,re

mientras que un DFS esperaría que fuera

UNA,si,mi,re,do

Θ(V+mi)O(V)

Estoy de acuerdo, el problema no es trivial.

Aryabhata
fuente
55
Esto supone que las listas de adyacencia tienen un orden específico fijo. Al menos en matemática, uno los ve como un conjunto, y un gráfico tiene múltiples recorridos de orden de profundidad, dependiendo de cómo iteres a los niños. (Imagine usar hashes para niños). En ese sentido, ABECD sigue siendo un orden de profundidad. El interlocutor se pregunta si existe un contraejemplo incluso en este contexto. (De hecho, aquí es donde comienza a complicarse.)
rgrig
3
remire
1
@Arybhata: Oh, lo siento, no sé por qué estaba asumiendo que querías decir que los bordes estuvieran dirigidos y apuntando hacia abajo. No están dirigidos, por lo que tiene razón: este es un contraejemplo incluso para lo que estaba diciendo en el comentario. (Esto es extraño: tuve que escribir mal su identificador, para que SE no lo elimine.)
rgrig