mirror of
https://github.com/Steffo99/unisteffo.git
synced 2024-11-25 17:34:20 +00:00
935 B
935 B
Depth-First Search
La depth-first search è un algoritmo che visita tutti i sottoalberi di un figlio prima di passare ad un altro sfruttando la natura ricorsiva degli alberi.
Funzionamento
Ci sono diverse versioni della depth-first search: ognuna visita la radice in un momento diverso.
DFS previsita (pre-order)
La DFS pre-visita visita la radice per prima, poi tutti i sottoalberi formati dai figli uno dopo l'altro.
- Visita radice
- dfs_pre_order(figlio1)
- dfs_pre_order(figlio2)
Postvisita (post-order)
La DFS postvisita visita prima tutti i sottoalberi dei figli, e alla fine la radice.
- dfs_post_order(figlio1)
- dfs_post_order(figlio2)
- Visita radice
Invisita (in-order)
La DFS invisita visita un certo numero di figli, poi la radice, e infine i figli restanti.
- dfs_in_order(figlio1, 1)
- Visita radice
- dfs_in_order(figlio2, 1)