Esercizio 22vertici influenzabili e vertici entro distanza d

Parte A: vertici influenzabili

Idea

$x$ è influenzabile se sta nella stessa componente connessa di un influencer. Si lancia una visita (BFS o DFS, 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 →) da ogni influencer non ancora visitato: ogni vertice raggiunto è nella componente di un influencer. Al termine si contano i vertici visitati che non sono influencer.

Altra scelta: ogni influencer è una sorgente di una BFS; se un influencer è già visitato (perché nella componente di un altro) non serve ripartire, e la visita non riparte mai su vertici già visitati: ogni vertice è esaminato una sola volta.

Pseudocodice

Algoritmo Influenzabili(G)
Input: grafo G=(V,E) con liste di adiacenza; campo influencer di ogni vertice
Output: numero di vertici non influencer che stanno nella componente connessa di un influencer
forall v in V do v.ID <- 0
conta <- 0
forall v in V do
    if v.influencer = 1 AND v.ID = 0 then
        BFS(G, v)                       (visita tutta la componente di v ponendo ID <- 1)
forall v in V do
    if v.ID = 1 AND v.influencer = 0 then conta <- conta + 1
return conta

(In alternativa si conta durante la visita: ogni volta che si inserisce in lista un vertice $w$ con influencer = 0 si incrementa conta.)

Complessità

Ogni vertice viene scoperto al più una volta in tutte le chiamate (dopo la prima visita ha ID $\ne 0$) e ogni arco viene esaminato al più due volte (una per estremo), quindi le BFS costano in totale $O(n + m)$. I due cicli sui vertici costano $\Theta(n)$. Totale $\Theta(n + m)$ con le liste di adiacenza.

Esempio. Vertici $1, \dots, 6$, archi $12, 23, 45$ (il vertice $6$ è isolato), influencer: $1$ e $6$. La BFS da $1$ visita $\{1, 2, 3\}$; $6$ è un influencer non visitato: la BFS visita solo $\{6\}$. Non influencer visitati: $2$ e $3$ $\Rightarrow$ $2$ influenzabili ($4$ e $5$ stanno in una componente senza influencer). (Confronto con il calcolo delle componenti su 500 grafi casuali: risultati uguali.)

Parte B: vertici a distanza al più $d$

Idea

La BFS da $s$ visita i vertici per livelli $L_i$ secondo la distanza $i$ da $s$ (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 →). Basta fermarsi al livello $d$: i vertici dei livelli $L_0, \dots, L_d$ sono esattamente quelli a distanza $\le d$.

Esempio: cammino $s - a - b - c$ con un vertice $x$ adiacente ad $a$ e a $c$. $L_0 = \{s\}$, $L_1 = \{a\}$, $L_2 = \{b, x\}$, $L_3 = \{c\}$. Per $d = 2$ la risposta è $4$ ($s, a, b, x$); per $d = 1$ è $2$; per $d = 0$ è $1$ (solo $s$).

Pseudocodice

Algoritmo contaEntro(G, s, d)
Input: grafo G (liste di adiacenza), vertice s, intero d >= 0; tutti gli ID valgono 0 e le label null
Output: numero di vertici a distanza <= d da s
s.ID <- 1; L0 <- lista con s; i <- 0; conta <- 1
while i < d AND Li non è vuota do
    Li+1 <- lista vuota
    forall v in Li do
        forall e in G.incidentEdges(v) do
            w <- G.opposite(v, e)
            if w.ID = 0 then
                w.ID <- 1; inserisci w in Li+1; conta <- conta + 1
    i <- i + 1
return conta

Qui non occorre etichettare gli archi: basta il controllo su ID dei vertici. Se serve il risultato per tutti i vertici $v$ (primo testo), si ripete per ciascuno, riportando gli ID a $0$ ad ogni giro: $\Theta(n(n + m))$.

Complessità

Ogni vertice entra in una lista al più una volta e di ciascun vertice dei livelli $L_0, \dots, L_{d-1}$ si scorre la lista di adiacenza: costo $O(n_d + m_d)$, dove $n_d$ ed $m_d$ sono vertici e archi coinvolti. Nel caso pessimo, $O(n + m)$ per una sorgente. (Controllato con una implementazione confrontata con il calcolo di tutte le distanze su 300 grafi casuali.)

Errori comuni

• Parte A: contare anche gli influencer, o contare i vertici di tutte le componenti (anche senza influencer).
• Parte A: rilanciare la BFS da ogni influencer senza controllare ID: ogni componente verrebbe visitata più volte, ma si può ancora arrivare a $O(n \cdot (n + m))$ se molti influencer stanno nella stessa componente.
• Parte B: usare la DFS (non dà le distanze minime) o arrestare la BFS al livello $d - 1$ o $d + 1$.
• Dimenticare che il grafo può essere sconnesso: la BFS visita solo la componente di $s$ e i vertici fuori restano a distanza $\infty$.