центральный узел в дереве

Question

Учитывая дерево, как найти центральный узел в дереве, чтобы расстояние от центрального узла до других узлов было минимальным (при условии, что каждое ребро имеет удельный вес)? Я пытаюсь использовать DFS, но возможно ли это сделать за линейное время?

Answer 1

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

Пример:

   *                 *              
  / \                 \
 *   *                 *              *
      \                 \              \
       *      =>         *     =>       *    =>   *
        \                 \                     
         *                 *
          \
           *

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

Answer 2

Вот еще один подход, который также работает в O(V).

Выберите любую вершину v1 в вашем дереве.Запустите BFS из этой вершины.Последняя вершина (v2), которую вы пройдете, будет самой дальней вершиной из v1.Теперь запустите другую BFS, на этот раз из вершины v2 и получите последнюю вершину v3.

Путь от v2 до v3 - это диаметр дерева, и ваш центр лежит где-то на нем,Точнее, он находится в середине этого.Если путь имеет 2n + 1 точек, будет только 1 центр (в позиции n + 1).Если путь имеет 2n точек, в позициях n и n + 1.

будет два центра. Вы используете только 2 вызова BFS, которые выполняются в 2 * O(V) времени.