Diametro di un albero (Editoriale)

Il diametro di un albero è la lunghezza del percorso più lungo nell'albero. In altre parole, dobbiamo trovare due vertici $a$ e $b$ tali che la distanza tra loro sia massima.

Per risolvere questo problema, utilizziamo il seguente algoritmo:

• Innanzitutto, eseguiamo una ricerca in profondità (depth-first search) a partire da un vertice qualsiasi dell'albero, ad esempio il vertice $1$. Durante questo attraversamento, troviamo il vertice che si trova alla distanza massima dal punto di partenza. Indichiamo questo vertice con $a$.

• Successivamente, eseguiamo un'altra ricerca in profondità, questa volta a partire dal vertice $a$. Come risultato di questo attraversamento, troviamo il vertice più lontano da $a$ e lo indichiamo con $b$.

Allora, la distanza tra i vertici $a$ e $b$ è la massima tra tutte le coppie di vertici dell'albero e, quindi, è uguale al diametro dell'albero.

Esempio

Consideriamo l'albero dell'esempio.

Il diametro dell'albero è $3$. La distanza massima si ottiene, ad esempio, tra i vertici $2$ e $5$.

Esercizio

Trova il diametro dell'albero.

Implementazione dell'algoritmo

Memorizziamo l'albero in input nella lista di adiacenza $g$. Memorizziamo le distanze minime dalla sorgente a ciascun vertice nell'array $dist$.

vector<vector<int>> g;
vector<int> dist;

La funzione dfs esegue una ricerca in profondità a partire dal vertice $v$. La distanza minima dalla sorgente al vertice $v$ è $d$. Il genitore del vertice $v$ nella ricerca in profondità è $p$.

void dfs(int v, int d, int p = -1)
{

Memorizziamo la distanza minima dalla sorgente al vertice $v$ in dist[v].

  dist[v] = d;

Scorriamo tutti gli archi (v, to). Per ogni figlio to del vertice $v$ (dove $to$ non è il genitore di $v$) avviamo una ricerca in profondità. La distanza dalla sorgente al vertice $to$ sarà d + 1.

  for (int to : g[v])
    if (to != p) dfs(to, d + 1, v);
}

La parte principale del programma. Leggiamo i dati in input.

scanf("%d", &n);
g.resize(n + 1);
dist.resize(n + 1);

Costruiamo un albero non orientato.

for (i = 1; i < n; i++)
{
  scanf("%d %d", &u, &v);
  g[u].push_back(v);
  g[v].push_back(u);
}

Troviamo le distanze minime dal vertice $1$ a tutti gli altri vertici. Il vertice più lontano da esso è $a$.

dfs(1, 0, -1);
a = max_element(dist.begin(), dist.begin() + n + 1) – 
                dist.begin();

Troviamo le distanze minime dal vertice $b$ a tutti gli altri vertici. Il vertice più lontano da esso è $b$.

dfs(a, 0,  -1);
b = max_element(dist.begin(), dist.begin() + n + 1) – 
                dist.begin();

Stampiamo il diametro dell'albero — la distanza minima da $a$ a $b$.

printf("%d\n", dist[b]);