Линейный алгоритм нахождения диаметра дерева

Question

У меня есть следующий код, чтобы найти диаметр дерева:

ALGORITHM: TREE_DIAMETER (T) 

maxlength ← 0 
for s ← 0 to s < |V[T]| 
     do temp ← BSF(T, S) 
      if maxlength < temp 
        maxlength ← temp 
        increment s by 1 
return maxlength 

Но этот алгоритм не работает в линейном времени. Сохраняя детали вышеописанного кода как можно больше (например: используя BSF), можно ли оптимизировать его до линейного времени? Вы можете использовать псевдокод.

Answer 1

Вот простой алгоритм с линейной временной сложностью:
1) Выберите произвольную вершину v.
2) Найдите самую удаленную вершину от v с помощью BFS (назовем ее u).
3) Найдите дальнейшую вершину от u, используя BFS еще раз (назовем ее t).
Тогда distance(u, t) - это диаметр.
BFS вызывается только дважды, поэтому временная сложность линейна.

Answer 2

Как дополняющий другой ответ, доказательство может быть сделано следующим образом:

Давайте сначала обозначим два конца диаметра в дереве, как s и t, а функция d(u, v) обозначает расстояние между узлом u и узел v.

Теперь мы выбираем произвольный узел X, то есть 2 случая:

1. X находится на диаметре;
2. X является не на диаметре.

Для случая 1, легко видеть, что при этом (2) (второй шаг алгоритма, описанного в @ user2040251 отвечают), то мы получим либо d(X, s) или d(X, t). Если мы получим что-то еще, скажем d(X, u), то u и s или t могут сформировать более длинный путь, чем d(s, t), что противоречит факту. Поэтому, выполняя (3), мы получим d(s, t).

В случае 2, выполнив (2), мы имеем 2 случая:

1. Самый длинный путь, начиная с X содержит, по меньшей мере, 1 балл по диаметру;
2. Самый длинный путь от X не делится любой баллы с диаметром.

В случае 2.1, давайте обозначим первого пересечения в Y. Из-за случая 1 мы знаем, что самый длинный путь от Yдолжен заканчиваться либо s, либо t. Поэтому в этом случае самый длинный путь, начинающийся с X, должен заканчиваться либо s, либо t. Следовательно, сделав (3), получим d(s, t).

Для случая 2.2, обозначим другой конец самого длинного пути, начиная с X, как Z. Поскольку ни X или Z находится на диаметре, и с учетом X, Z, s, t находятся на одном дереве, можно сделать вывод, что должен быть узлом V на пути X к Z, ссылки на узел W на путь s до t. Потому что X до Z является самым длинным путем, начиная с X, поэтому d(X, V) + d(V, W) + d(W, t) < d(X, Z). Аналогично, мы имеем d(Z, V) + d(V, W) + d(W, s) < d(X, Z). Добавление их и упрощение даст нам: d(X, Z) > 2d(V, W) + d(s, t) > d(s, t), что противоречит тому, что s - t - это диаметр.

график, который иллюстрирует случай 2.2:

s    Z 
|    | 
|    | 
|    | 
W-------------V 
|    | 
|    | 
|    | 
t    X 

Таким образом, мы имеем:

d(X, V) + d(V, W) + d(W, t) < d(X, Z) потому X к Z самый длинный путь, начиная с X;

d(Z, V) + d(V, W) + d(W, s) < d(X, Z) т.к. X до Z самый длинный путь, начинающийся с Z;

Сложение 2 выражения:

d(X, Z) + 2d(V, W) + d(s, t) < 2d(X, Z)

Наконец, мы имеем d(X, Z) > 2d(V, W) + d(s, t) > d(s, t), что противоречит тот факт.