19
правок
Изменения
м
→Алгоритм для дерева за O(n)
Собственно, алгоритм нахождения центра описан в доказательстве теоремы.
* Пройдёмся по дереву [[Обход_в_глубину,_цвета_вершин|обходом в глубину]] и поместим в очередь все висячие вершины ("листья"). Пометим их числом 0.
* Пока в очереди не останется одна вершина или две, помеченные одинаковым числом, будем удалять из графа вершину, находящуюся в начале очереди. Во время удаления необходимо поместить её предка в конец очереди (если он ещё не помещён) и пометить большим на единицу числом, затем извлечь вершину из очереди.
