Изменения
Нет описания правки
Возьмём вершину <tex> u </tex> такую,что <tex>d[u] \ge d[t]</tex> для любого <tex>t</tex>.Снова найдём расстояние от <tex>u</tex> до всех остальных вершин. Самое большое расстояние {{---}} диаметр дерева.
Расстояние до остальных вершин будем искать алгоритмом <tex>BFS</tex>.
{
v = u = w = 0;
d = bfs(g,v);
for (i = 0; i < n; i++)
if (d[i] > d[u])
u = i;
bfs(g,u);
for (i = 0; i < n; i++)
if (d[i] > d[w])
== Обоснование корректности ==
Будем пользоваться свойством,что в любом дереве больше одного листа. Исключительный случай-дерево из одной вершины,но алгоритм сработает верно и в этом случае.
Искомое расстояние - есть расстояние между двумя листами.
|proof=
Пусть искомое расстояние - есть расстояние между вершинами <tex>a,b</tex> где <tex>b</tex> - не является листом. Т.к. b не является листом, то значит её степень <tex>></tex> 1 => из неё существует ребро в непосещенную вершину (дважды посетить вершину <tex>b</tex> мы не можем). Лемма доказана.
}}
В дереве BFS не существует ребер между вершинами из разных поддеревьев некоторого их общего предка.
|proof=
Предположим существует ребро <tex>u,v</tex> между соседними поддеревьями:
Рассмотрим первую вершину в которую приведет наш алгоритм, предположим это вершина <tex>u</tex>, тогда в ходе рассмотрения всех смежных вершин <tex>u</tex> мы добавим в список вершину <tex>v</tex>, тем самым исключив возможность попадания их в разные поддеревья.
}}
== Оценка производительности ==
Все операции кроме <tex>BFS</tex> {{---}} <tex>O(1)</tex>.
<tex>BFS</tex> работает линейное время,запускаем мы его 2 раза.Получаем <tex>O(V + E)</tex>.
