Esercizio 23escursioni e componenti connesse

(a) Strategia

Ogni escursione copre una componente connessa (vedi Grafi - definizioni e proprietàGrafo G=(V,E) diretto e non diretto, grafo semplice e pesato; incidenza, adiacenza, grado; cammini, cicli, sottografi, grafi connessi e componenti connesse; alberi liberi, foreste, spanning tree e spanning forest; proprietà con dimostrazioni (somma dei gradi = 2m, m <= n(n-1)/2, alberi m = n-1, connessi m >= n-1, foreste m <= n-1).Grafi - definizioni e proprietà →). Quindi:

• il numero minimo di escursioni è il numero di componenti connesse (non se ne possono fare meno: due vertici di componenti diverse non stanno nella stessa escursione; e con una escursione per componente si coprono tutti);
• il numero di punti nell'escursione più lunga è la dimensione della componente più grande.

Si usa la BFS (la DFS va ugualmente bene, vedi Visite di grafi - BFS e DFSVisite in ampiezza (BFS) e in profondità (DFS) come design pattern; etichette discovery, cross e back edge; BFS tree e distanze; complessità Theta(n+m) con liste di adiacenza; applicazioni (connettività, componenti, spanning tree, cammini minimi non pesati, cicli, vertici a distanza al più d); esempio svolto su un grafo di 7 vertici.Visite di grafi - BFS e DFS →). Si scorrono i vertici: appena se ne trova uno non visitato ($v$.ID $= 0$) si è trovata una nuova componente e si lancia la visita da lì. Modifica: la visita conta i vertici che scopre, con un contatore count azzerato a ogni visita; ogni vertice scoperto riceve come ID il valore corrente del contatore (positivo: serve solo a distinguere "visitato" da "non visitato", e a ricordare l'ordine di scoperta). Il valore finale di count è la dimensione della componente appena esplorata. La BFS modificata, BFS-COUNT(G, v), restituisce questo valore.

Esempio: $7$ punti, sentieri $1\!-\!2$, $2\!-\!3$, $3\!-\!4$, $5\!-\!6$ (il punto $7$ è isolato). Si lancia la BFS da $1$: scopre $1, 2, 3, 4$ e restituisce $4$; si passa a $5$ (non visitato): scopre $5, 6$ e restituisce $2$; $7$ è non visitato: restituisce $1$. Risultato: $3$ escursioni, la più lunga con $4$ punti.

(b) Pseudocodice

Algoritmo planExcursions(G)
Input: grafo non orientato G=(V,E) con liste di adiacenza; per ogni v, v.ID = 0 (non visitato)
Output: (numExcursions, maxSize): numero di componenti connesse e dimensione della maggiore
numExcursions <- 0; maxSize <- 0
forall v in V do
    if v.ID = 0 then
        numExcursions <- numExcursions + 1
        size <- BFS-COUNT(G, v)
        if size > maxSize then maxSize <- size
return (numExcursions, maxSize)

Algoritmo BFS-COUNT(G, s)           (BFS di G, s con una modifica)
count <- 1; s.ID <- count; L0 <- lista con s
mentre la lista di livello corrente non è vuota: per ogni vertice v del livello
    per ogni arco e incidente su v: sia w il vertice opposto
        se w.ID = 0 allora count <- count + 1; w.ID <- count; w va nel livello successivo
return count

(Se $G$ non è vuoto, maxSize $\ge 1$.) Il contatore è azzerato a ogni chiamata, quindi gli identificatori sono progressivi all'interno della singola visita: non serve che siano distinti tra componenti diverse.

(c) Complessità

Ogni vertice viene scoperto, e inserito nelle liste della BFS, una sola volta in tutte le chiamate (dopo la scoperta ha ID $\ne 0$, quindi non genera altre visite). Con le liste di adiacenza di una visita si scorre per ogni vertice la sua lista, e ogni arco compare in due liste (una per estremo, grafo non orientato): ogni arco è esaminato due volte. Il ciclo esterno sui vertici costa $\Theta(n)$. In totale:

$$\Theta(n + m).$$

Se il grafo fosse rappresentato con matrice di adiacenza scorrere i vicini di un vertice costerebbe $\Theta(n)$ e il totale salirebbe a $\Theta(n^2)$; con la sola lista degli archi $L_E$ ogni visita costerebbe $\Theta(m)$ per vertice, quindi $\Theta(nm)$ (vedi Rappresentazione dei grafiStrutture di base (lista dei vertici LV, lista degli archi LE), liste di adiacenza, matrice di adiacenza; operazioni incidentEdges, opposite, areAdjacent; spazio e tempi a confronto; esempio con un grafo di 5 vertici.Rappresentazione dei grafi →). Lo stesso conteggio vale se si usa la DFS al posto della BFS. (Controllato con una implementazione confrontata con un calcolo diretto delle componenti su 300 grafi casuali.)

Errori comuni

• Lanciare la BFS da ogni vertice senza controllare ID: ogni componente verrebbe visitata più volte, con costo $\Theta(n(n+m))$ al caso pessimo.
• Non azzerare il contatore tra una visita e l'altra: la dimensione della componente risulterebbe cumulativa.
• Contare le escursioni come il numero di vertici o di archi, o restituire solo una delle due informazioni.
• Dimenticare di specificare (come chiede il testo) il collegamento tra la complessità e la rappresentazione del grafo.