Il cammino più lungo in un albero (Editoriale)

Il cammino più breve in un albero pesato può essere trovato tramite una ricerca in profondità o in ampiezza (in questo caso non è necessario utilizzare l'algoritmo di Dijkstra).

Per trovare il cammino più lungo (il diametro dell'albero) procediamo come segue:

1. Eseguiamo una ricerca in ampiezza a partire dal primo vertice. Troviamo il vertice $v$, per il quale il cammino sarà il più lungo.

2. Successivamente eseguiamo una ricerca in ampiezza a partire dal vertice $v$ e determiniamo il vertice $u$, per il quale il cammino sarà anch'esso il più lungo.

3. Il cammino da $v$ a $u$ è il più lungo nell'albero (il diametro dell'albero).

Esempio

L'albero presentato nell'esempio ha il seguente aspetto:

• Eseguiamo una ricerca in ampiezza a partire dal vertice $1$ (a sinistra). Il cammino più lungo sarà fino al vertice $4$.

• Successivamente eseguiamo una ricerca in ampiezza a partire dal vertice $4$ (a destra). Il cammino più lungo risulterà essere fino al vertice $3$, la sua lunghezza è pari a $12$.

Implementazione dell'algoritmo

Dichiariamo la lista di adiacenza del grafo $g$.

Dichiariamo l'array delle distanze più brevi $d$.

vector<vector<pair<int, int>>> g;
vector<long long> d;

La funzione bfs esegue una ricerca in ampiezza a partire dal vertice $v$.

int bfs(int v)
{
  deque<int> q;
  q.push_back(v);
  while (!q.empty())
  {
    int v = q.front(); q.pop_front();
    for (auto x : g[v])
    {
      int to = x.first;
      int w = x.second;
      if (d[to] == -1)
      {
        d[to] = d[v] + w;
        q.push_back(to);
      }
    }
  }

Restituiamo il numero del vertice per il quale la distanza dal vertice $v$ è massima.

  return max_element(d.begin() + 1, d.begin() + n + 1) - d.begin();
}

Parte principale del programma. Leggiamo i dati in input. Costruiamo il grafo.

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

for (i = 0; i < n - 1; i++)
{
  scanf("%d %d %lld", &b, &e, &dist);
  g[b].push_back({ e, dist });
  g[e].push_back({ b, dist });
}

Inizializziamo l'array delle distanze più brevi.

d = vector<long long>(n + 1, -1);
d[1] = 0;

Eseguiamo la prima ricerca in ampiezza a partire dal vertice $1$. Determiniamo il vertice $v$, che si trova più lontano da $1$.

int v = bfs(1);

Inizializziamo nuovamente l'array delle distanze più brevi e avviamo la seconda ricerca in ampiezza, a partire dal vertice $v$.

d = vector<long long>(n + 1, -1);
d[v] = 0;
v = bfs(v);

Stampiamo la risposta — la lunghezza del cammino più lungo.

printf("%lld\n", d[v]);

Implementazione dell'algoritmo — ricerca in profondità

Memorizziamo la lista di adiacenza del grafo nell'array $g$.

Per memorizzare le distanze più brevi dichiariamo l'array $dist$.

vector<vector<pair<int, int>> > g;
vector<long long> dist;

La funzione dfs esegue una ricerca in profondità a partire dal vertice $v$. Il vertice $p$ è il predecessore di $v$ nel processo di ricerca in profondità.

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

Esaminiamo tutti gli archi adiacenti al vertice $v$.

  for (auto x : g[v])
  {

Consideriamo l'arco v → to con peso $w$.

    int to = x.first;
    int w = x.second;

Se to \ne p, ricalcoliamo dist[to] e richiamiamo la ricerca in profondità a partire dal vertice $to$.

    if (to != p)
    {
      dist[to] = dist[v] + w;
      dfs(to, v);
    }
  }
}

Parte principale del programma. Leggiamo i dati in input. Costruiamo il grafo.

scanf("%d", &n);
g.resize(n + 1);
for (i = 0; i < n - 1; i++)
{
  scanf("%d %d %d", &b, &e, &w);
  g[b].push_back({ e, w });
  g[e].push_back({ b, w });
}

Eseguiamo una ricerca in profondità a partire dal vertice $1$. Riempiamo l'array delle distanze più brevi $dist$ a partire dal vertice $1$.

dist.assign(n + 1, -1);
dist[1] = 0;
dfs(1);

Determiniamo il vertice $v$, la cui distanza dal vertice $1$ è massima.

v = max_element(dist.begin(), dist.end()) - dist.begin();

Eseguiamo la seconda ricerca in profondità, a partire dal vertice $v$. Riempiamo l'array delle distanze più brevi $dist$ a partire dal vertice $v$.

dist.assign(n + 1, -1);
dist[v] = 0;
dfs(v);

Il valore massimo nell'array $dist$ è pari al diametro dell'albero.

v = max_element(dist.begin(), dist.end()) - dist.begin();

Stampiamo la risposta.

printf("%lld\n", dist[v]);

Implementazione in Python

from collections import deque

Leggiamo i dati in input. Memorizziamo la lista di adiacenza del grafo in $g$.

Dichiariamo la lista delle distanze più brevi $d$.

n = int(input())
g = [[] for _ in range(n + 1)]
d = [-1] * (n + 1)

Costruiamo il grafo.

for _ in range(n - 1):
  b, e, dist = map(int, input().split())
  g[b].append((e, dist))
  g[e].append((b, dist))

La funzione bfs esegue una ricerca in ampiezza a partire dal vertice $v$.

def bfs(v):
  q = deque()
  q.append(v)

  while q:
    v = q.popleft()
    for to, w in g[v]:
      if d[to] == -1:
        d[to] = d[v] + w
        q.append(to)

Restituiamo il numero del vertice per il quale la distanza dal vertice $v$ è massima.

  return d.index(max(d))

Eseguiamo la prima ricerca in ampiezza a partire dal vertice $1$. Determiniamo il vertice $v$, che si trova più lontano da $1$.

d[1] = 0
v = bfs(1)

Inizializziamo l'array delle distanze più brevi e avviamo la seconda ricerca in ampiezza a partire dal vertice $v$.

d = [-1] * (n + 1)
d[v] = 0
v = bfs(v)

Stampiamo la risposta — la lunghezza del cammino più lungo.

print(d[v])