1
Fork 0
mirror of https://github.com/Steffo99/unisteffo.git synced 2024-11-25 17:34:20 +00:00
triennale-appunti-steffo/public/materials/year1/algoritmi/17_DepthFirstSearch.md

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.

  1. Visita radice
  2. dfs_pre_order(figlio1)
  3. dfs_pre_order(figlio2)

Postvisita (post-order)

La DFS postvisita visita prima tutti i sottoalberi dei figli, e alla fine la radice.

  1. dfs_post_order(figlio1)
  2. dfs_post_order(figlio2)
  3. Visita radice

Invisita (in-order)

La DFS invisita visita un certo numero di figli, poi la radice, e infine i figli restanti.

  1. dfs_in_order(figlio1, 1)
  2. Visita radice
  3. dfs_in_order(figlio2, 1)