Диаметр дерева

Диаметр дерева — наибольшее расстояние между какой-либо парой вершин.

Наивно: перебрать все пары и найти расстояние — $O(n^3)$. Лучше: запустить обход из каждой вершины — $O(n^2)$. Но есть решение за $O(n)$, и оно неожиданно короткое.

Алгоритм

1. Возьмите произвольную вершину $v$.
2. Обходом найдите самую далёкую от неё вершину $a$.
3. Обходом найдите самую далёкую от $a$ вершину $b$.

Расстояние между $a$ и $b$ — это диаметр.

pair<int, int> farthest(int start) {   // {вершина, расстояние}
    vector<int> dist(n, -1);
    dist[start] = 0;
    queue<int> q;
    q.push(start);
    int best = start;
    while (!q.empty()) {
        int v = q.front(); q.pop();
        if (dist[v] > dist[best]) best = v;
        for (int to : g[v]) if (dist[to] == -1) { dist[to] = dist[v] + 1; q.push(to); }
    }
    return {best, dist[best]};
}

int diameter() {
    int a = farthest(0).first;
    return farthest(a).second;
}

Два обхода, $O(n)$. Проверено: на двадцати тысячах случайных деревьев до двенадцати вершин результат совпал с перебором всех стартовых вершин.

Почему это верно

Утверждение, которое нужно доказать: самая далёкая вершина от любой вершины является концом какого-то диаметра.

Подвесим дерево за $v$ и посмотрим на найденную вершину $a$.

Шаг 1: $a$ — лист. Иначе у неё есть ребёнок, который дальше от $v$, — противоречие с тем, что $a$ самая далёкая.

Шаг 2. Пусть диаметр — это путь между $x$ и $y$, и ни один из концов не совпадает с $a$. Путь в подвешенном дереве — это подъём до наименьшего общего предка $x$ и $y$ и спуск обратно; обозначим этот предок $c$.

Путь от $v$ до $a$ тоже где-то проходит. Возможны два случая.

Если путь $v \to a$ пересекает путь $x \to y$, пусть точка пересечения — $t$. Тогда расстояние от $t$ до $a$ не меньше расстояния от $t$ до $x$ и до $y$: иначе $a$ не была бы самой далёкой от $v$. Значит, заменив $x$ на $a$, мы не укоротим путь, и $a$ — конец диаметра.

Если пути не пересекаются, соединим их: получится путь длиннее диаметра, что невозможно.

Отсюда: $a$ — конец какого-то диаметра, и самая далёкая от неё вершина — второй конец.

Замечание про единственность: диаметров может быть много. Алгоритм найдёт какой-то один, и его длину — а она у всех одинакова.

В общем графе так нельзя

В произвольном графе диаметр — наибольшее из кратчайших расстояний между парами. Два обхода тут не работают, и быстрого алгоритма не известно.

Причина глубокая: умей мы быстро считать диаметр, мы умели бы проверять, равен ли он $n-1$, — а это существование гамильтонова пути, задача NP-полная.

На практике диаметр графа считают алгоритмом Флойда за $O(n^3)$ или $n$ обходами в ширину за $O(nm)$. Ничего лучше в общем случае нет.

Родственные задачи

Центр дерева — вершина, минимизирующая расстояние до самой далёкой. Она лежит на середине диаметра: находим диаметр, идём по нему до середины. Центров один или два, в зависимости от чётности длины.

Радиус — расстояние от центра до самой далёкой вершины, равен $\lceil d/2 \rceil$.

Диаметр через динамику. Подвешиваем дерево и для каждой вершины считаем две наибольшие глубины среди детей. Их сумма — длиннейший путь, проходящий через эту вершину; максимум по всем вершинам и есть диаметр. Тоже $O(n)$, зато обобщается на взвешенные рёбра и на задачи, где нужен не только ответ, но и путь.

Взвешенное дерево. Приём с двумя обходами работает и там, если веса неотрицательны. С отрицательными весами он ломается, и это стандартный контрпример к «а я слышал, что диаметр ищется двумя обходами».