Центр node в дереве

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

Ответы

Ответ 1

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

Пример:

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

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

Ответ 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) времени.