Ən uzun yol ağacda (Həll təhlili)

Çəkili ağacda ən qısa yolu dərinliyə görə axtarış və ya enliyə görə axtarış vasitəsilə tapmaq olar (bu halda Dijkstra alqoritmindən istifadə etmək mütləq deyil).

Ən uzun yolu (ağacın diametrini) tapmaq üçün aşağıdakı kimi hərəkət edirik:

1. Birinci təpədən enliyə görə axtarış aparaq. Yolun ən böyük olacağı $v$ təpəsini tapaq.

2. Sonra $v$ təpəsindən enliyə görə axtarış işə salaq və yolun yenə də ən böyük olacağı $u$ təpəsini müəyyən edək.

3. $v$-dən $u$-ya olan yol ağacdakı ən uzun yoldur (ağacın diametridir).

Misal

Misalda təqdim olunan ağac aşağıdakı görünüşə malikdir:

• $1$ təpəsindən (solda) enliyə görə axtarış aparaq. Ən uzun yol $4$ təpəsinə qədər olacaq.

• Sonra $4$ təpəsindən (sağda) enliyə görə axtarış işə salaq. Ən uzun yol $3$ təpəsinə qədər olacaq, onun uzunluğu $12$-yə bərabərdir.

Alqoritmin realizasiyası

Qrafın qonşuluq siyahısını $g$ elan edək.

Ən qısa məsafələr massivini $d$ elan edək.

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

bfs funksiyası $v$ təpəsindən enliyə görə axtarış aparır.

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);
      }
    }
  }

$v$ təpəsindən məsafəsi maksimal olan təpənin nömrəsini qaytarırıq.

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

Proqramın əsas hissəsi. Giriş məlumatlarını oxuyuruq. Qrafı qururuq.

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 });
}

Ən qısa məsafələr massivini işə salırıq.

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

$1$ təpəsindən birinci enliyə görə axtarışı yerinə yetiririk. $1$-dən ən uzaqda olan $v$ təpəsini müəyyən edirik.

int v = bfs(1);

Ən qısa məsafələr massivini yenidən işə salırıq və $v$ təpəsindən başlayaraq ikinci enliyə görə axtarışı işə salırıq.

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

Cavabı — ən böyük yolun uzunluğunu çap edirik.

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

Alqoritmin realizasiyası — dərinliyə görə axtarış

Qrafın qonşuluq siyahısını $g$ massivində saxlayırıq.

Ən qısa məsafələri saxlamaq üçün $dist$ massivini elan edək.

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

dfs funksiyası $v$ təpəsindən dərinliyə görə axtarış aparır. $p$ təpəsi dərinliyə görə axtarış prosesində $v$-nin sələfidir.

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

$v$ təpəsinə qonşu olan bütün tillərin üzərindən keçirik.

  for (auto x : g[v])
  {

$w$ çəkili v → to tilinə baxırıq.

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

Əgər to \ne p olarsa, dist[to]-nu yenidən hesablayırıq və $to$ təpəsindən dərinliyə görə axtarışı çağırırıq.

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

Proqramın əsas hissəsi. Giriş məlumatlarını oxuyuruq. Qrafı qururuq.

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 });
}

$1$ təpəsindən dərinliyə görə axtarışı yerinə yetiririk. $1$ təpəsindən $dist$ ən qısa məsafələr massivini doldururuq.

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

$1$ təpəsindən məsafəsi maksimal olan $v$ təpəsini müəyyən edirik.

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

$v$ təpəsindən başlayaraq ikinci dərinliyə görə axtarışı yerinə yetiririk. $v$ təpəsindən $dist$ ən qısa məsafələr massivini doldururuq.

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

$dist$ massivindəki ən böyük qiymət ağacın diametrinə bərabərdir.

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

Cavabı çap edirik.

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

Python realizasiyası

from collections import deque

Giriş məlumatlarını oxuyuruq. Qrafın qonşuluq siyahısını $g$-də saxlayırıq.

Ən qısa məsafələr siyahısını $d$ elan edirik.

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

Qrafı qururuq.

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

bfs funksiyası $v$ təpəsindən enliyə görə axtarış aparır.

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)

$v$ təpəsindən məsafəsi maksimal olan təpənin nömrəsini qaytarırıq.

  return d.index(max(d))

$1$ təpəsindən birinci enliyə görə axtarışı yerinə yetiririk. $1$-dən ən uzaqda olan $v$ təpəsini müəyyən edirik.

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

Ən qısa məsafələr massivini işə salırıq və $v$ təpəsindən ikinci enliyə görə axtarışı işə salırıq.

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

Cavabı — ən böyük yolun uzunluğunu çap edirik.

print(d[v])