Предложите, чтобы некоторый алгоритм нашел узел в дереве, расстояние которого до его самого дальнего узла минимально среди всех узлов

Выберите произвольный узел v в дереве T . Запустите BFS, создавая v как корень T . BFS выводит расстояния от v до всех остальных узлов из Т .

Теперь выберите узел u , наиболее удаленный от v . Снова запустите BFS, сделав u корнем. {{1} } На выходе нового расстояния найдите узел 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 . У нас есть два случая:

a) u --- r и v - k имеют общий узел o . Тогда v - o - u и v - o - r короче, чем u --- o --- k . Тогда o --- r короче, чем o --- k . Тогда u --- o --- r не самый длинный путь в графе, потому что u --- o --- k длиннее. Это противоречит нашему предположению.

б) u --- r и v - k не имеют общих узлов. Но поскольку граф связан, на каждом из этих путей есть узлы o1 и o2 , так что путь между ними o1 - o2 не содержат любые другие узлы на этих двух путях. Противоречие с предположением такое же, как в пункте a), но с o1 - o2 вместо простого o (на самом деле, точка a просто частный случай b , где o1 = o2 ).

Это доказывает утверждение и, следовательно, правильность алгоритма.

(это доказательство, написанное Павлом Шведом , и у первоначального автора могло быть более короткое).

Удалите листья. Если осталось более 2 узлов, повторите. Оставшийся узел (или 2 узла) будет искомым узлом.

Почему это работает:

Узел(ы) находится в середине самого длинного пути P в дереве. Их максимальное расстояние до любого узла составляет не более половины длины пути (иначе он не был бы самым длинным). Любой другой узел на P, очевидно, будет иметь большее расстояние до дальнейшего конца P, чем найденный узел (узлы). Любой узел n не на P будет иметь самый дальний узел по крайней мере (расстояние от n до ближайшего узла на P, скажем c) + (расстояние от c до дальнейшего конца P), поэтому снова больше, чем узел(ы), найденные алгоритмом.

Вы можете использовать алгоритм Дейкстры ( http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm ) на каждом узле в поверните, чтобы найти все расстояния от этого узла до каждого другого узла; просканируйте полученный список, чтобы узнать расстояние до самого дальнего узла. После того, как вы выполните Dijkstra'd каждый узел, еще одно сканирование даст вам минимум этих максимальных расстояний.

Дейкстра обычно считается имеющей время выполнения O (v ^ 2) , где v - количество узлов; вы бы запускали его один раз для каждого узла, что увеличит время до O (v ^ 3) в наивной реализации. Вы можете получить выгоду, сохранив результаты прогонов Дейкстры более ранних узлов и используя их как известные значения в последующих прогонах.

Вы можете использовать алгоритм Джонсона для разреженных графов, но в противном случае используйте алгоритм Флойда-Варшалла просто потому, что он реализовать несложно.

По сути, вы хотите найти расстояние от каждого узла до каждого другого узла, а затем просто выполнить тривиальный поиск нужного свойства.

Как другие говорили в комментариях: Дерево - это граф, точнее, неориентированный связный ациклический граф - см. «Дерево» (теория графов) .