Si ottiene DFS se si cambia la coda a una pila in un'implementazione BFS?

Question

Ecco il pseudocodice standard per ricerca in ampiezza:

{ 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

Qui push e pop si presume siano operazioni di coda. Ma cosa succede se si tratta di operazioni di stack? Fa le conseguenti vertici algoritmo di visita al fine in profondità?

---

Se avete votato per il commento "questo è banale", mi chiederei di spiegare perché è banale. Trovo il problema abbastanza difficile.

Answer 1

No, questo non è lo stesso di un DFS.

Si consideri il grafico

Se si spingono i nodi in diritto di ordine sinistra, l'algoritmo ti dà un attraversamento:

$ A, B, E, C, D $

, mentre un DFS si aspetterebbe che fosse

$ A, B, E, D, C $

Il problema si verifica perché si contrassegna come visto al momento di spingere, piuttosto che al momento della visita. Come fuori punte nei commenti, se si contrassegna al momento della visita, i requisiti di spazio potrebbe andare fino a $ \ Theta (V + E) $ piuttosto che $ \ mathcal {} O (V) $.

Sono d'accordo, il problema non è banale.