Выберите произвольный узел v в дереве T .
Запустите BFS, делая v в качестве корня T .
BFS выводит расстояния от v до всех остальных узлов T .
Теперь выберите узел u , который находится дальше всего от v .
Запустите BFS снова, сделав u в качестве пользователя root.
На новом выходе расстояния найдите узел w , который находится дальше всего от u .
Рассмотрим путь между u и w .
Это самый длинный путь в дереве T .
Узел в середине пути - это центр дерева T .
Обратите внимание, что в дереве может существовать два центра. Если это так, то они соседи.
Производительность: O (n) , где n - количество узлов T .
Доказательство
Заявка : лист ( u ), наиболее удаленный от некоторого узла v , лежит на самом длинном пути.
Если мы докажем это, тогда алгоритм верен, так как сначала он находит u , и, поскольку это один конец самого длинного пути, использует DFS для поиска самого этого пути.
Доказательство претензии : Давайте использовать retucto ad absurdum. Предположим, u --- r - самый длинный путь в дереве; и для некоторого узла v ни v --- u , ни v --- r не является самым длинным путем из v . Вместо этого самый длинный путь - v --- k . У нас есть два случая:
а) u --- r и v - k имеют общий узел o . Тогда v-o-u и v-o-r короче u --- o --- k . Тогда o --- r короче o --- k . Тогда u --- o --- r не самый длинный путь в графе, потому что u --- o --- k длиннее. Это противоречит нашему предположению.
b) u --- r и v - k не имеют общих узлов. Но поскольку граф связан, на каждом из этих путей есть узлы o1 и o2 , так что путь между ними o1 - o2 не содержат любые другие узлы на этих двух путях. Противоречие с предположением такое же, как в пункте а), но с o1 - o2 вместо простого o (на самом деле точка a просто особый случай b , где o1 = o2 ).
Это доказывает утверждение и, следовательно, правильность алгоритма.
(это доказательство, написанное Павлом Шведом , и первоначальный автор может иметь более короткое).