Найдовший шлях у дереві (Розбір)

Найкоротший шлях у зваженому дереві можна знайти за допомогою пошуку в глибину або в ширину (використання алгоритму Дейкстри в даному випадку не є обов'язковим).

Для знаходження найдовшого шляху (діаметра дерева) діємо наступним чином:

1. Виконаємо пошук в ширину з першої вершини. Знайдемо вершину $v$, до якої шлях буде найбільшим.

2. Потім запустимо пошук в ширину з вершини $v$ і визначимо вершину $u$, до якої шлях також буде найбільшим.

3. Шлях від $v$ до $u$ є найдовшим у дереві (діаметром дерева).

Приклад

Дерево, представлене у прикладі, має наступний вигляд:

• Виконаємо пошук в ширину з вершини $1$ (зліва). Найдовший шлях буде до вершини $4$.

• Потім запустимо пошук в ширину з вершини $4$ (справа). Найдовший шлях виявиться до вершини $3$, його довжина рівна $12$.

Реалізація алгоритму

Оголосимо список суміжності графа $g$.

Оголосимо масив найкоротших відстаней $d$.

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

Функція bfs виконує пошук в ширину з вершини $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);
      }
    }
  }

Повертаємо номер вершини, до якої відстань від вершини $v$ максимальна.

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

Основна частина програми. Читаємо вхідні дані. Будуємо граф.

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

Ініціалізуємо масив найкоротших відстаней.

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

Виконуємо перший пошук в ширину з вершини $1$. Визначаємо вершину $v$, яка знаходиться найдалі від $1$.

int v = bfs(1);

Знову ініціалізуємо масив найкоротших відстаней і запускаємо другий пошук в ширину, починаючи з вершини $v$.

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

Виводимо відповідь — довжину найбільшого шляху.

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

Реалізація алгоритму — пошук в глибину

Список суміжності графа зберігаємо в масиві $g$.

Для зберігання найкоротших відстаней оголосимо масив $dist$.

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

Функція dfs виконує пошук в глибину з вершини $v$. Вершина $p$ є предком $v$ у процесі пошуку в глибину.

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

Перебираємо всі ребра, суміжні з вершиною $v$.

  for (auto x : g[v])
  {

Розглядаємо ребро v → to з вагою $w$.

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

Якщо to \ne p, перераховуємо dist[to] і викликаємо пошук в глибину з вершини $to$.

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

Основна частина програми. Читаємо вхідні дані. Будуємо граф.

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$. Заповнюємо масив найкоротших відстаней $dist$ від вершини $1$.

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

Визначаємо вершину $v$, відстань до якої від вершини $1$ максимальна.

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

Виконуємо другий пошук в глибину, починаючи з вершини $v$. Заповнюємо масив найкоротших відстаней $dist$ від вершини $v$.

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

Найбільше значення в масиві $dist$ дорівнює діаметру дерева.

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

Виводимо відповідь.

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

Python реалізація

from collections import deque

Читаємо вхідні дані. Список суміжності графа зберігаємо в $g$.

Оголошуємо список найкоротших відстаней $d$.

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

Будуємо граф.

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

Функція bfs виконує пошук в ширину з вершини $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)

Повертаємо номер вершини, до якої відстань від вершини $v$ максимальна.

  return d.index(max(d))

Виконуємо перший пошук в ширину з вершини $1$. Визначаємо вершину $v$, яка знаходиться найдалі від $1$.

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

Ініціалізуємо масив найкоротших відстаней і запускаємо другий пошук в ширину з вершини $v$.

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

Виводимо відповідь — довжину найбільшого шляху.

print(d[v])