Connettività

• problema della connettività tra $s$ e $t$: dati due nodi $s$ e $t$, esiste un percorso tra $s$ e $t$?
• problema del percorso più corto tra $s$ e $t$: dati due nodi $s$ e $t$, qual è la lunghezza del percorso più corto tra $s$ e $t$?

Breadth First Search (visita in ampiezza)

<aside> 💡 BFS esplora il grafo a partire da una sorgente ****$s$ muovendosi in tutte le possibili direzioni e visitando i nodi livello per livello

</aside>

BFS algorithm

• $L_0 = \{s\}$
• $L_1=$ tutti i vicini di $s$
• $L_2=$ tutti i nodi che non appartengono a $L_0$ o $L_1$ e che sono uniti da un arco ad un nodo in $L_1$
• $L_{i+1} =$ tutti i nodi che non appartengono agli strati $L_0,..,L_i$ e che sono uniti da un arco ad un nodo in $L_i$

Teorema

Per ogni $i$, $L_i$ consiste di tutti i nodi a distanza $i$ da $s$

Di conseguenza, c’è un percorso da $s$ a $t$ se e solo se $t$ appare in $L_i$, per un certo $i \in \{0,..,j\}$

Pseudocodice

Breadth First Search (albero BFS)

<aside> 💡 L’algoritmo BFS 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 un vertice $v$ viene scoperto, cioè il momento in cui è visitato per la prima volta
  • ciò avviene durante l’esame dei vertici adiacenti ad un certo vertice $u$ di un certo livello $L_i$ (linea 6)
  • in questo momento, oltre ad aggiungere $v$ al livello $L_{i+1}$ (linea 8), aggiungiamo l’arco $(u,v)$ e il nodo $v$ all’albero

Proprietà