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