Диаметр корневого дерева

Question

Я пытаюсь найти алгоритм линейного времени, использующий рекурсию, для решения проблемы диаметра для корневого k-арного дерева, реализованного с помощью списков смежности.Диаметр дерева - это максимальное расстояние между любой парой листьев.Если я выберу корень r (то есть узел, степень которого> 1), можно показать, что диаметр - это либо максимальное расстояние между двумя листьями в одном поддереве, либо максимальное расстояние между двумя листьями путикоторые проходят через r.Мой псевдокод для этой задачи:

Tree-Diameter(T,r)
    if degree[r] = 1 then
        height[r] = 0
        return 0
    for each v in Adj[r] do
        for i = 1 to degree[r] - 1 do
            d_i = Tree-Diameter(T,v)
    height[r] = max_{v in Adj[r]} (height[v]
    return max(d_i, max_{v in V} (height[v]) + secmax_{v in V} (height[v], 0) + 1)

Чтобы получить линейное время, я вычисляю диаметр И высоту каждого поддерева одновременно.Затем я выбираю максимальное количество между диаметрами каждого поддерева и двумя самыми большими высотами дерева + 1 (функция secmax выбирает между height[v] и 0, потому что у некоторого поддерева может быть только дочерний элемент: в этомВ этом случае вторая по величине высота - 0).Я спрашиваю вас, работает ли этот алгоритм нормально, и если нет, в чем проблемы?Я попытался обобщить алгоритм, который решает ту же проблему для двоичного дерева, но я не знаю, является ли это хорошим обобщением.

Любая помощь приветствуется!Заранее спасибо!

Answer 1

Всего в дереве для нахождения диаметра выполните следующие действия:

1. Выберите случайный узел A , запустите BFS на этом узле, чтобы найти самый дальний узел из A .назовите этот узел как S .

2. Теперь запустите BFS, начиная с S , найдите самый дальний узел из S ,назовите его D .

Путь между S и D - это диаметр вашего дерева.Этот алгоритм O (n), и только два раза обходится дерево.Доказательство немного сложнее, но не сложно.(попробуй сам или если считаешь неправду, напишу позже).И будьте осторожны, я говорю о деревьях, а не общих графах.(В дереве нет петли, и он подключен).

Answer 2

Это реализация Python того, что, как мне кажется, вас интересует. Здесь дерево представлено в виде списка дочерних деревьев.

def process(tree):
  max_child_height=0
  secmax_child_height=0
  max_child_diameter=0
  for child in tree:
    child_height,child_diameter=process(child)
    if child_height>max_child_height:
      secmax_child_height=max_child_height
      max_child_height=child_height
    elif child_height>secmax_child_height:
      secmax_child_height=child_height
    if child_diameter>max_child_diameter:
      max_child_diameter=child_diameter
  height=max_child_height+1
  if len(tree)>1:
    diameter=max(max_child_diameter,max_child_height+secmax_child_height)
  else:
    diameter=max_child_diameter
  return height,diameter

def diameter(tree):
  height,diameter=process(tree)
  return diameter