DFS ricorsivo vs DFS iterativo

Question

Sto cercando di capire la differenza tra DFS ricorsivo e DFS iterativo. Quella con lo stack usa un approccio iterativo o ricorsivo?

Ad esempio, quale sarebbe l'output dell'utilizzo di una traversata ricorsiva DFS del grafico e una traversata iterativa DFS del grafico? I vicini vengono ripetuti in ordine alfabetico.

Heres il grafico:

Per un attraversamento DFS (quello con una pila, non so se la sua ricorsivo o iterativo) questo è quello che ho ottenuto: A, C, D, E, F. Qualcuno può confermare che tipo di DFS traversal è questo e come funzionerebbe l'altro? Grazie!

Answer 1

A mio parere, la versione ricorsiva e iterativa differisce solo nell'utilizzo dello stack. La versione ricorsiva utilizza lo stack di chiamate mentre la versione iterativa esegue esattamente gli stessi passaggi, ma utilizza uno stack definito dall'utente invece dello stack di chiamate. Non vi è alcuna differenza nella sequenza dei passaggi stessi (se si utilizzano regole di separazione appropriate per garantire una sequenza trasversale uguale per i nodi figlio, se necessario), quindi è impossibile esaminare l'output per decidere se è stata utilizzata un'implementazione iterativa o ricorsiva .

Answer 2

Come indicato nell'altra risposta, attraversando il grafico utilizzando DFS si visiteranno i vertici nello stesso modo indipendentemente dall'attuale implementazione DFS, utilizzando iterazione o ricorsione. Vedi pseudocodice su Wikipedia article.

Hai un requisito aggiuntivo che è quello di visitare i vertici adiacenti in ordine alfabetico. Ciò significa che lo stack deve essere ordinato quando si spinge qualcosa (nella versione iterativa) o significa che devi recitare sui vertici adiacenti in ordine ordinato (nella versione ricorsiva). Entrambe le implementazioni si comporteranno esattamente allo stesso modo.

Dato il vincolo di ordine alfabetico, il risultato A, C, D, E, F è l'unica traversata DFS possibile del grafico.