Avez-vous DFS si vous modifiez la file d'attente d'une pile dans une mise en œuvre BFS?

Question

Voici le pseudo-code standard pour la première recherche étendue:

{ 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

Ici push et pop sont supposés être des opérations de file d'attente. Mais si ce sont des opérations de la pile? Est-ce que les sommets de visite de l'algorithme résultant pour en profondeur d'abord?

---

Si vous avez voté pour le commentaire « cela est trivial », je vous demande d'expliquer pourquoi il est trivial. Je trouve le problème assez délicat.

Answer 1

Non, ce n'est pas le même que DFS.

Considérons le graphe

Si vous appuyez sur les nœuds de droite à gauche, l'algorithme vous donne un traversal:

$ A, B, E, C, D $

alors qu'un DFS s'attendre à ce qu'il soit

$ A, B, E, D, C $

Le problème se produit parce que vous le marquer comme on le voit au moment de pousser, plutôt que au moment de la visite. Comme en pointe dans les commentaires, si vous marquez au moment de la visite, vos besoins en espace pourraient aller jusqu'à $ \ theta (V + E) $ plutôt que $ \ mathcal {O} (V) $.

Je suis d'accord, le problème est pas trivial.