Il risultato finale dei vostri attraversamenti è corretto, sei abbastanza vicino. Tuttavia, sei un po 'fuori nei dettagli.
Nella prima ricerca di profondità, si aprirà un nodo, lo contrassegnerà come visitato e impilerà i suoi bambini non visitati. In questo ordine. L'ordine può sembrare irrilevante per un albero, ma se avessi un grafico con cicli, potresti cadere in un ciclo infinito, ma questa è un'altra discussione.
Data la linea di base dell'algoritmo, dopo aver spinto il nodo radice nello stack, si avvierà la prima iterazione, immediatamente scoppiando A. Non rimarrà nello stack fino alla fine dell'algoritmo. Azionerai A, ammucchi D, C e B tutti in una volta (o B, C e D, puoi farlo da sinistra a destra o da destra a sinistra, è la tua scelta) e segna A come visitato. In questo momento, il tuo stack ha D in basso, C in mezzo e B in alto.
Il nodo successivo spuntato è B. Spingete F ed E nello stack (terrò l'ordine uguale al vostro), contrassegnando B come visitato. La pila ha, dall'alto al basso, E F C D. Successivo, E viene spuntato, non vengono aggiunti nuovi nodi e E viene contrassegnato come visitato. Il ciclo continuerà, facendo lo stesso a F, C e D. L'ordine finale è ABEFC D.
Cercherò di riscrivere l'algoritmo in modo simile al vostro:
Push root into stack
Loop until stack is empty
Pop node N on top of stack
Mark N as visited
For each children M of N
If M has not been visited (M.visited() == false)
Push M on top of stack
ho vinto Entriamo nei dettagli della ricerca per ampiezza, l'algoritmo è esattamente lo stesso. La differenza sta nella struttura dei dati e come si comporta. Una coda è FIFO (First In First Out) e, per questo motivo, visiterai tutti i nodi nello stesso livello prima di iniziare a visitare i nodi nei livelli inferiori.
Nota: Non è molto efficiente o in tempo reale utilizzare DFS perché la quantità di possibilità diventa molto grande, quindi si utilizza BFS per ottenere uno spostamento ragionevole basato su alcuni calcoli. Non è così rilevante qui, ma potresti voler esaminare l'algoritmo di Minimax per l'intelligenza artificiale perché è relativamente semplice e dimostra di ridurre la quantità di possibilità per ottenere una mossa molto più veloce (di solito in Tic-tac-toe). – wazy
@wazy dipenderà dai dati.Cosa succede se il grafico ha più nodi per livello che per altezza? –
Odio dire che "dipende", ma è abbastanza fiducioso stai cercando di trovare una soluzione "rapidamente" (o almeno tentando e non necessariamente ottimale) o stai cercando di valutare ogni possibile soluzione/combinazione. – wazy