Изменения
Нет описания правки
Возьмём вершину <tex> u </tex> такую,что <tex>d[u] >= d[t]</tex> для любого <tex>t</tex>.Снова найдём расстояние от <tex>u</tex> до всех остальных вершин.Самое большое расстояние - диаметр дерева.
Расстояние до остальных вершин удобно будем искать алгоритмом <tex>BFS</tex>.
== Реализация ==
{
v = u = w = 0;
d = bfs(g,v); // заполняет массив d[n] кратчайшими расстояниями до всех вершин.
for(i = 0; i < n; i++)
if (d[i] > d[u])
== Обоснование корректности ==
Будем пользоваться свойством,что в любом дереве >= 2 листов(имеют степень один)больше одного листа.Исключительный случай-дерево из одной вершины,но алгоритм сработает верное и в этом случае.
{{Теорема
|statement=
В дереве BFS не существует ребер между вершинами из разных поддеревьев некоторого из их общего предка.
|proof=
Такое же как у дерева dfs.
* [http://neerc.ifmo.ru/wiki/index.php?title=%D0%9E%D0%B1%D1%85%D0%BE%D0%B4_%D0%B2_%D0%B3%D0%BB%D1%83%D0%B1%D0%B8%D0%BD%D1%83,_%D1%86%D0%B2%D0%B5%D1%82%D0%B0_%D0%B2%D0%B5%D1%80%D1%88%D0%B8%D0%BD#.D0.94.D0.B5.D1.80.D0.B5.D0.B2.D0.BE_.D0.BE.D0.B1.D1.85.D0.BE.D0.B4.D0.B0_.D0.B2_.D0.B3.D0.BB.D1.83.D0.B1.D0.B8.D0.BD.D1.83]
}}
