Для дерева, как найти центр node в дереве, чтобы расстояние от центрального node до других узлов было минимальным (при условии, что каждое ребро имеет единичный вес)? Я пытаюсь использовать DFS, но возможно ли это сделать в линейном времени?
Центр node в дереве
Ответ 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)
времени.