Esercizio 4

Sia dato un grafo non orientato con $n$ nodi e $m$ archi. Vogliamo produrre un elenco delle componenti connesse del grafo, disposte in ordine non crescente di dimensione. Supponiamo, ad esempio, che ogni componente connessa sia rappresentata dal nodo di minimo indice presente in essa.
Dare una descrizione di un algoritmo, avente complessità $O(m+n),$ per questo problema, sottolineando tutti gli aspetti che è necessario considerare per ottenere un tale risultato.

Supponiamo che i nodi del grafo siano numerati da $1$ a $n.$ Teniamo un array $A$ che memorizzi, per ogni nodo, il nome della componente connessa nella quale esso si trova, ossia l'indice del minimo nodo cui è connesso. Inizializziamo tutto l'array a zero, per dire che nessun nodo è ancora classificato (se la numerazione dei nodi partisse da zero, ovviamente, per l'inizializzazione si dovrebbe usare un valore del tipo $-1.$)

Si scandisce poi l'array, soffermandosi su ogni nodo $i$ per cui $A[i]$ è uguale a zero. Per un tale nodo, si effettua una visita BFS della sua componente connessa; per ogni nodo incontrato $n,$ si pone $A[n]=i.$ Alla fine, tutti gli indici dell'array saranno diversi da zero.

A questo punto conviene servirsi di un altro array $C$ nel quale alla fine vogliamo avere $C[i]=0$ se $i$ non è rappresentante di alcuna componente; $C[i]=k$ se $i$ è rappresentante di una componente di dimensione $k.$ Il calcolo del contenuto di $C$, facendo uso di $A,$ è banale.

Notando che $C$ contiene numeri compresi tra 0 e $n$, possiamo ora ordinare i nodi con un algoritmo lineare e stabile, usando come chiave del nodo $i$ proprio $C[i]$. Cosí facendo, tutti i nodi che non sono rappresentanti finiscono in fondo. Gli altri forniscono l'elenco secondo le specifiche desiderate.