#AlberiDopo aver introdotto i grafi e alcuni algoritmi utili per ricavare informazioni da essi, vale la pena concentrarsi su un tipo particolare di grafo: l’albero.
0
1
2
3
4
5
Figure 1: Un esempio di albero con 6 nodi
Un albero è un grafo connesso con esattamente 𝑁−1 archi, dove 𝑁 è il numero di nodi.
Questo fatto implica diverse proprietà, la più importante delle quali è che gli alberi non contengono cicli1. Ciò implica a sua volta che tra due nodi dell’albero esiste un solo cammino che li collega. È bene notare che vale anche l’implicazione inversa, cioè se un grafo è connesso e aciclico, allora è un albero e ha esattamente 𝑁−1 archi.
Grazie all’unicità del cammino tra ogni coppia di nodi, spesso un problema su alberi si risolve in maniera più efficiente rispetto allo stesso problema su grafi generici. Ad esempio, puoi trovare il cammino più breve (nonché l’unico!) tra due nodi con una DFS o una BFS, anche nel caso in cui gli archi abbiano un peso.
Quando un nodo ha grado 1, ovvero ha un solo arco uscente, viene detto foglia. Nell’albero in figura, le foglie sono i nodi 2, 3 e 5. Tutti gli alberi con più di un nodo contengono sempre almeno 2 foglie.
#Alberi radicatiMolti algoritmi su albero prevedono la scelta di un nodo speciale, detto radice, per dare un ordine all’albero. Se non viene specificata la radice nel testo del problema, la sua scelta è arbitraria2.
La scelta di una radice permette di definire per tutti i nodi, a eccezione della radice, un nodo genitore (in inglese parent node). Il genitore del nodo 𝑖 è l’ultimo nodo che si visita muovendosi dalla radice al nodo 𝑖. Si dice inoltre che un nodo 𝑗 è figlio del nodo 𝑖 se 𝑖 è il genitore di 𝑗.
Nell’albero sopra illustrato, prendendo come radice il nodo 0, si ha per esempio che i nodi 2 e 3 sono figli del nodo 1, mentre il nodo 4 è il genitore del nodo 5. L’array 𝑃 tale per cui 𝑃[𝑖] contiene il genitore del nodo 𝑖 (o −1 se il nodo 𝑖 è la radice) è detto parent array. Il parent array dell’albero sopra, radicato in 0, sarebbe [−1,0,1,1,0,4].
La profondità di un nodo è il numero di archi che lo separano dalla radice. La profondità della radice è 0. Nell’esempio sopra, i nodi 1 e 4 sono a profondità 1, mentre i nodi 2,3 e 5 sono a profondità 2. I nodi a profondità massima in un albero sono sempre foglie.
Gli antenati di un nodo 𝑖 sono i nodi sul cammino dalla radice fino al nodo stesso. Gli antenati del nodo 5 nell’esempio sopra sono i nodi 4 e 1. Il più basso antenato comune di due nodi 𝑖 e 𝑗, in inglese lowest common ancestor (LCA), è il nodo 𝑘 alla massima profondità che è antenato sia di 𝑖 sia di 𝑗: diremo LCA(𝑖,𝑗)=𝑘. Se 𝑖 è antenato di 𝑗, l’LCA è 𝑖. Viceversa se 𝑗 è antenato di 𝑖. Nell’esempio sopra LCA(2,3)= 1, LCA(2,5)=0 e LCA(0,3)=0.
Trovare l’LCA tra due nodi è estremamente utile per svolgere numerose query su albero. Vedremo in seguito come calcolarlo in maniera efficiente.
Un ultimo concetto utile nell’ambito degli alberi radicati è quello di sottoalbero: il sottoalbero di un nodo 𝑖 è l’insieme di tutti i nodi che hanno 𝑖 tra gli antenati, 𝑖 compreso.
#Alberi particolariAlcuni tipi di albero particolari assumono nomi specifici:
0
1
2
3
0
1
2
3
4
5
6
7
0
1
2
3
4
5
6
Linea con 4 nodiStella con centro 0Albero binario completo con 7 nodi
Le linee sono alberi in cui ogni nodo ha grado 1 o 2; questa condizione è sufficiente a verificare che l’albero sia una linea. Le stelle hanno un solo nodo con grado maggiore di 1. Questo nodo è detto centro della stella e tutti gli altri nodi sono adiacenti a esso. Negli alberi binari ogni nodo ha al più due figli. Spesso questo tipo di albero viene utilizzato per strutture dati come segment tree e alberi binari di ricerca.
#Visite su alberoCome per i grafi generici, un albero può essere esplorato attraverso BFS e DFS.
void dfs(int i, int parent) {
// esploro il nodo i
for (int j : adj[i])
if (j != parent)
dfs(j, i);
}
Poiché esploriamo un albero, non è necessario tenere traccia dei nodi visitati ed è sufficiente non risalire verso il genitore. L’ordine in cui si visitano i nodi attraverso una visita in profondità è detto dfs-order. Per come funziona la DFS, il dfs-order trasforma sottoalberi in sottoarray. Il dato di un dfs-order e, per ogni nodo, il relativo sottoarray è detto albero linearizzato3.
Vediamo un problema in cui serve visitare ricorsivamente l’albero.
Convegno Aziendale
Ci viene dato l’albero delle gerarchie tra gli 𝑁 dipendenti di un’azienda e siamo interessati al numero di coppie di dipendenti (𝑎,𝑏) tali che 𝑎 è antenato di 𝑏 nella gerarchia.
Prova il problema online: https://training.olinfo.it/task/mat_convegno
Soluzione
Invece di provare tutte le coppie, possiamo fissare 𝑎. Per un dato 𝑎, il numero di coppie che ci interessano è dato dalla dimensione del sottoalbero di 𝑎 tolto il nodo 𝑎 stesso. Notiamo che il sottoalbero è ben definito dal momento che l’albero è radicato.
Sia 𝑆𝑖 la dimensione del sottoalbero del nodo 𝑖. Per calcolarla sommiamo gli 𝑆𝑗 dove 𝑗 è un nodo figlio di 𝑖.
È chiaro che questo tipo di calcolo vada eseguito ricorsivamente, dal momento che per calcolare la dimensione del sottoalbero di un nodo occorre aver prima calcolato quella dei figli.
vector<vector<int>> adj;
int totale = 0;
int dfs(int i) {
int sottoalbero = 0;
for (int j : adj[i])
sottoalbero += dfs(j);
totale += sottoalbero;
return sottoalbero + 1;
}
int coppie(int N, int* C) {
adj.resize(N);
int root;
for (int i = 0; i < N; i++) {
if (C[i] != -1) {
adj[C[i]].push_back(i);
} else {
root = i;
}
}
dfs(root);
return totale;
}
#Problemi consigliati
Road Reparation (https://cses.fi/problemset/task/1675)
Noci di cocco (https://training.olinfo.it/task/preoii_machete)
Codex Botanicus (https://training.olinfo.it/task/oii_botanicus)
Tour de Treeland (https://training.olinfo.it/task/iiot_tourdetree)
1Si può dimostrare facilmente per induzione.2Solitamente si usa il nodo 0 o, in contesti 1-based, il nodo 1.3Tieni a mente questo concetto per quando saremo capaci di svolgere operazioni interessanti su sequenze di numeri.