Si ottiene DFS se si cambia la coda a una pila in un'implementazione BFS?
-
16-10-2019 - |
Domanda
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.
Soluzione
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.