В алгоритмической проблеме, которую я пытаюсь решить - я в ситуации, когда мне дано дерево, и мне нужно выбрать узел как корень, для которого высота дерева была бы минимальной.Выбор корня дерева, так что высота дерева минимальна
Есть 200 000 узлов и 150 000 ребер. Из-за ограничения по времени мне нужен лучший алгоритм, чем O(n^2).
Какой алгоритм я могу использовать?
Выберите любой узел и предположите, что это корень. Запустите DFS, чтобы найти расстояние до самого дальнего листа. Это будет в основном вычислять высоту дерева, если вы выберете первый узел как root.
Далее вы найдете правильный корень, найдя центр дерева. Для этого вы смотрите на детей текущего корня и выбираете ту, которая имеет наибольшую высоту (наибольшее расстояние до самого дальнего листа). Если вы переместите корень к этому ребенку, новая высота будет минимальной между значением, которое у вас уже есть в этом узле, и 1 + следующим самым большим значением из других листьев текущего корня. Вы применяете это, перемещая корень, пока вы больше не сможете уменьшить высоту. Это один из центров дерева (может быть больше) и решение, которое вы ищете.
Inital DFS - O (N). Оптимизируя расстояние, вы не можете посещать узел дважды, а каждый шаг O (1) амортизируется, поэтому в целом это O (N). O (1) амортизируется, потому что у узла может быть много детей, но вы считаете их только один раз (после того, как вы переместитесь, вы не сможете вернуться, чтобы вы не могли проверить их снова), поэтому, даже если вы проверите все дерево, вы проверите O (N) в целом.
Я думаю, что центр дерева должен быть требуемым узлом как корень дерева, потому что максимальное расстояние от корня до любого узла минимально, если корень является центром дерева.
Итак, то, что вы ищете, называется центром дерева, о котором говорилось [здесь] (http://stackoverflow.com/questions/4020122/finding-center-of-the-tree) –
@ PhamTrung: Хорошо. Спасибо. Я не знал термин центр дерева. Почему бы вам не опубликовать его как ответ, чтобы я мог выбрать его как лучший ответ? – Donotalo