Componenti connesse

<aside> 💡 Sottoinsieme di vertici tale che per ciascuna coppia di vertici $u$ e $v$ esiste un percorso tra $u$ e $v$

</aside>

componente connessa contenente $s$: trova tutti i nodi raggiungibili da $s$
- come trovarla: esegui BFS o DFS utilizzando $s$ come sorgente
insieme di tutte le componenti connesse: trova tutte le componenti connesse
- come trovarlo: fino a quando ci sono nodi che non sono stati esplorati, scegli uno di questi nodi ed esegui BFS (o DFS) su $u$ utilizzando questo nodo come sorgente

Per ogni due nodi $s$ e $t$ di un grafo, le loro componenti connesse o sono uguali o sono disgiunte

Il teorema precedente implica che le componenti connesse di un grafo sono a due a due disgiunte

Algoritmo per trovare l’insieme di tutte le componenti connesse:

Untitled

BFS modificata in modo tale che nella fase di inizializzazione non vengano settate a False le entrate dell’array Discovered

Al posto della BFS possiamo usare la DFS con l’array Explored

Indichiamo con $k$ il numero di componenti connesse

Indichiamo con $n_i$ e con $m_i$ rispettivamente il numero di nodi e di archi della componente $i$-esima

l’esecuzione della visita BFS o DFS sulla componente i-esima richiede tempo $O(n_i + m_i)$
il tempo totale richiesto da tutte le visite BFS o DFS è $\Sigma_{i=1}^k O(n_i + m_i)= O(\Sigma_{i = 1}^k (n_i+m_i))$
poichè le componenti sono a due a due disgiunte ù, si ha che $\Sigma_{i=1}^k O(n_i + m_i)=n+m$
e il tempo totale di esecuzione dell’algoritmo che scopre le componenti connesse è $O(n)+O(n+m)=O(n+m)$