Depth first search (visita in profondità)

<aside> 💡 La visita DFS parte dalla sorgente $s$ e si spinge in profondità fino a che non è possibile raggiungere nuovi nodi

</aside>

• la visita parte da $s$, segue uno degli archi uscenti da $s$ ed esplora il vertice $v$ a cui porta l’arco
• una volta in $v$, se c’è un arco uscente da $v$ che porta in un vertice $w$ non ancora esplorato allora l’algoritmo esplora $w$
• uno volta in $w$ segue uno degli archi uscenti da $w$ e così via fino a che non arriva in un nodo del quale sono già stati esplorati tutti i vicini
• a questo punto l’algoritmo fa backtrack (torna indietro) fino a che torna in un vertice a partire dal quale può visitare un vertice non ancora esplorato in precedenza

Pseudocodice

$R$ = insieme dei vertici raggiunti

Analisi: $O(n+m)$

• se ignoriamo il tempo delle chiamate ricorsive al suo interno, ciascuna visita ricorsiva richiede tempo $O(1+deg(u))$: $O(1)$ per marcare $u$ e aggiungerlo ad $R$ e $O(deg(u))$ per eseguire il for
• se inizialmente invochiamo DFS su un nodo $s$, allora viene invocata ricorsivamente su tutti i nodi raggiungibili a partire da $s$
• il costo totale è quindi al più $\Sigma_{u \in V} O(1+deg(u))=O(\Sigma_{u \in V}1+ \Sigma_{u \in V}deg(u))=O(n+m)$

Depth First Search Tree

<aside> 💡 L’algoritmo DFS produce un albero che ha come radice la sorgente $s$ e come nodi tutti i nodi del grafo raggiungibili da $s$

</aside>

L’albero si ottiene in questo modo:

• consideriamo il momento in cui viene invocata DFS(v)
  • ciò avviene durante l’esecuzione di DFS(u) per un certo nodo $u$; in particolare durante l’esame dell’arco $(u,v)$ nella chiamata DFS(u)
  • in questo momento, aggiungiamo l’arco $(u,v)$ e il nodo $v$ all’albero

Albero DFS

<aside> 💡 Proprietà 1: per una data chiamata ricorsiva DFS(u), tutti i nodi che vengono etichettati come “Esplorati” tra l’inizio e la fine della chiamata DFS(u), sono discendenti di $u$ nell’albero DFS

</aside>

Albero DFS