Изменения
Нет описания правки
Алгоритм в этой статье находит диаметр в дереве.
Пусть дан граф <tex>G = <V, E></tex> Тогда диаметром <tex>d</tex> называется <tex>\max\limits_{u, v \in V} dist(v, u)</tex>, где <tex>dist </tex> — кратчайшнее расстояние между вершинами
== Алгоритм ==
<tex>d = min\{ v , u \subset graph, v \ne u \}</tex> <tex>dist(v, u) </tex>
Возьмём вершину <tex> u </tex> такую,что <tex>d[u] >= d[t] </tex> для любого <tex>t</tex>.Снова найдём расстояние от <tex>u</tex> до всех остальных вершин.Самое большое расстояние - диаметр дерева.
Расстояние до остальных вершин удобно искать алгоритмом BFS.
