Существует этот стандартный алгоритм поиска самого длинного пути в ненаправленных деревьях с использованием двух поисков в глубину:
- Запустите DFS из случайной вершины и найдите самую дальнюю из нее; скажи это .
- Теперь запустите DFS из чтобы найти самую дальнюю вершину. Этот путь является самым длинным путем в графе.
Вопрос в том, можно ли сделать это более эффективно? Можем ли мы сделать это с одной DFS или BFS?
(Это можно эквивалентно описать как проблему вычисления диаметра ненаправленного дерева.)
algorithms
graphs
trees
Emmy
источник
источник
Ответы:
Мы выполняем поиск в глубину по порядку и собираем результаты по пути, то есть рекурсивно решаем проблему.
Для каждого узла с (в дереве поиска) существует два случая:v u1,…,uk
Во втором случае мы должны объединить один или два самых длинных пути из в одно из поддеревьев; это, безусловно, те, что до самых глубоких листьев. Длина пути тогда если , или если , с множественный набор высот поддерева¹.v H(k)+H(k−1)+2 k>1 H(k)+1 k=1 H={h(Tui)∣i=1,…,k}
В псевдокоде алгоритм выглядит так:
источник
height1 + height2
это длина этого пути. Если это действительно самый длинный путь, его выбираетmax
. Это также объясняется в тексте выше, так что я не совсем понимаю вашу проблему? Конечно, вы должны выполнить повторение, чтобы выяснить, действительно ли это самый длинный путь, и даже если нет, это не помешает (относительно правильности) повторения.height2
явно снимаетheight1
с рассмотрения, так как же он может выбрать одного и того же потомка дважды? Это также было объяснено во вступительном тексте.longestPathHeight(T)
возвращает пару(h,d)
, гдеh
высотаT
иd
диаметрT
. (Верно?)Это может быть решено в лучшую сторону. Кроме того, мы можем уменьшить временную сложность до O (n) с небольшим изменением структуры данных и используя итеративный подход. Для подробного анализа и нескольких способов решения этой проблемы с различными структурами данных.
Вот краткое изложение того, что я хочу объяснить в моем блоге :
Рекурсивный подход - диаметр дерева. Другой способ решения этой проблемы заключается в следующем. Как мы уже упоминали выше, диаметр может
Это означает, что диаметр может быть идеально получен
И мы знаем, что диаметр - это самый длинный путь, поэтому мы берем максимум 1 и 2 на случай, если он лежит на одной из боковых сторон, или на 3, если он проходит через корень.
Итерационный подход - диаметр дерева
У нас есть дерево, нам нужна мета-информация с каждым узлом, чтобы каждый узел знал следующее:
Как только у каждого узла есть эта информация, нам нужна временная переменная для отслеживания максимального пути. Ко времени завершения алгоритма у нас есть значение диаметра в переменной temp.
Теперь нам нужно решить эту проблему восходящим подходом, потому что мы понятия не имеем о трех значениях для корня. Но мы знаем эти значения для листьев.
Шаги для решения
В данном узле
источник
Ниже приведен код, который возвращает путь диаметра, используя только один обход DFS. Требуется дополнительное пространство для отслеживания наилучшего видимого диаметра, а также самого длинного пути, начинающегося в конкретном узле дерева. Это подход динамического программирования, основанный на том факте, что путь с самым длинным диаметром либо не содержит корня, либо является комбинацией двух самых длинных путей соседей корня. Таким образом, нам нужно два вектора, чтобы отслеживать эту информацию.
источник