Диаметр дерева двумя обходами: почему два BFS/DFS дают правильный ответ?
Нужно найти диаметр дерева (длину самого длинного простого пути). Везде советуют: запустить BFS/DFS из произвольной вершины, найти самую далёкую вершину A, потом из A снова BFS/DFS, найти самую далёкую B — расстояние A–B и есть диаметр. Но почему это работает? Не верится, что произвольный старт даёт верный конец диаметра.
2 ответа
Алгоритм:
- BFS/DFS из любой вершины s → находим максимально удалённую вершину A.
- BFS/DFS из A → находим максимально удалённую вершину B.
dist(A,B)— диаметр.
pair<int,int> farthest(int src, int n, vector<int> g[]) {
vector<int> dist(n, -1); queue<int> q;
dist[src] = 0; q.push(src);
int best = src;
while (!q.empty()) {
int v = q.front(); q.pop();
if (dist[v] > dist[best]) best = v;
for (int u : g[v]) if (dist[u] == -1) { dist[u] = dist[v]+1; q.push(u); }
}
return {best, dist[best]};
}
int diameter(int n, vector<int> g[]) {
int a = farthest(0, n, g).first;
return farthest(a, n, g).second;
}
Почему A — обязательно конец какого-то диаметра. Ключевая лемма: самая удалённая от любой вершины s вершина A является концом некоторого диаметра дерева. Доказательство от противного: пусть диаметр — путь (u,w), а A не его конец. Рассматривая, где путь от s входит в путь (u,w), и используя, что A — самая дальняя от s, получаем, что заменив один конец диаметра на A, мы не уменьшим длину — значит A тоже конец диаметра. (В дереве пути единственны, что и делает рассуждение корректным.)
Дальше: раз A — конец диаметра, самая дальняя от A вершина — это другой его конец. Отсюда шаг 2 даёт точную длину.
Сложность O(V) (в дереве E = V−1), память O(V). Работает только на деревьях (для общего графа с весами/циклами — неверно)!
Важное предупреждение: «два обхода» дают диаметр только для дерева (и для невзвешенного или взвешенного с неотрицательными весами — тогда вместо BFS берут DFS/Дейкстру по дереву). Для произвольного графа с циклами метод неверен, там диаметр считается иначе (например, все пары кратчайших).
Альтернатива одним DFS (без доказательной леммы) — считать для каждой вершины две наибольшие глубины поддеревьев и обновлять ответ суммой двух максимумов:
int best = 0;
int dfs(int v, int p) { // возвращает макс. глубину вниз
int m1 = 0, m2 = 0;
for (int u : g[v]) if (u != p) {
int h = dfs(u, v) + 1;
if (h > m1) { m2 = m1; m1 = h; }
else if (h > m2) m2 = h;
}
best = max(best, m1 + m2); // путь через v
return m1;
}
Тоже O(V), удобно для взвешенных деревьев (замените +1 на вес ребра). И не ловит проблему со стеком на «дереве-цепочке» — для больших V переписывайте под итеративный DFS.