Visita di grafi direzionati

• raggiungibilità con direzione: dato un nodo $s$, trova tutti i nodi raggiungibili da $s$
• problema del più corto percorso diretto da $s$ a $t$: dati due nodi $s$ e $t$, qual è la lunghezza del percorso più corto da $s$ a $t$?
• visita di un grafo: le visite BFS e DFS si estendono naturalmente ai grafi direzionati
  • quando si esaminano gli archi incidenti su un certo vertice $u$, si considerano solo quelli uscenti da $u$
• web crawler: comincia dalla pagina web $s$; trova tutte le pagine raggiungibili a partire da $s$, sia direttamente che indirettamente

Connettività forte

I nodi $u$ e $v$ sono mutualmente raggiungibili se c’è un percorso da $u$ a $v$

<aside> 💡 Un grafo in cui ogni coppia di nodi è mutualmente raggiungibile si dice fortemente connesso

</aside>

Lemma

Sia $s$ un qualsiasi nodo di un grafo direzionato $G$

<aside> 💡 $G$ è fortemente connesso se e solo se ogni nodo è raggiungibile da $s$ ed $s$ è raggiungibile da ogni nodo

</aside>

Teorema

Si può determinare se $G$ è fortemente connesso in tempo $O(n+m)$

Algoritmo:

• prendi un qualsiasi nodo $s$
• esegui la BFS con sorgente $s$ in $G$
• crea il grafo $G^{rev}$ invertendo la direzione di ogni arco in $G$
• esegui la BFS con sorgente $s$ in $G^{rev}$
• restituisci true se e solo se tutti i nodi di $G$ vengono raggiunti in entrambe le esecuzioni della BFS
• la correttezza segue dal lemma precedente
  • la prima esecuzione trova i percorsi da $s$ a tutti gli altri nodi
  • la seconda esecuzione trova i percorsi da tutti gli altri nodi ad $s$ perchè avendo invertito gli archi un percorso da $s$ a $u$ è di fatto un percorso da $u$ ad $s$ nel grafo di partenza