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í push
y pop
se 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.
algorithms
graphs
rgrig
fuente
fuente
pop
a 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.Respuestas:
No, esto no es lo mismo que un DFS.
Considera la gráfica
Si empuja los nodos en orden de derecha a izquierda, el algoritmo le ofrece un recorrido:
mientras que un DFS esperaría que fuera
Estoy de acuerdo, el problema no es trivial.
fuente