Самый длинный путь в неориентированном дереве с одним обходом

44

Существует этот стандартный алгоритм поиска самого длинного пути в ненаправленных деревьях с использованием двух поисков в глубину:

  • Запустите DFS из случайной вершины и найдите самую дальнюю из нее; скажи это .vv
  • Теперь запустите DFS из чтобы найти самую дальнюю вершину. Этот путь является самым длинным путем в графе.v

Вопрос в том, можно ли сделать это более эффективно? Можем ли мы сделать это с одной DFS или BFS?

(Это можно эквивалентно описать как проблему вычисления диаметра ненаправленного дерева.)

Emmy
источник
2
То, что вы ищете, также называется диаметром дерева. (На деревьях «самый длинный кратчайший путь» и «самый длинный путь» - это одно и то же, поскольку существует только один путь, соединяющий любые два узла.)
Рафаэль

Ответы:

22

Мы выполняем поиск в глубину по порядку и собираем результаты по пути, то есть рекурсивно решаем проблему.

Для каждого узла с (в дереве поиска) существует два случая:vu1,,uk

  • Самый длинный путь в лежит в одном из поддеревьев .TvTu1,,Tuk
  • Самый длинный путь в содержит .Tvv

Во втором случае мы должны объединить один или два самых длинных пути из в одно из поддеревьев; это, безусловно, те, что до самых глубоких листьев. Длина пути тогда если , или если , с множественный набор высот поддерева¹.vH(k)+H(k1)+2k>1H(k)+1k=1H={h(Tui)i=1,,k}

В псевдокоде алгоритм выглядит так:

procedure longestPathLength(T : Tree) = helper(T)[2]

/* Recursive helper function that returns (h,p)
 * where h is the height of T and p the length
 * of the longest path of T (its diameter) */
procedure helper(T : Tree) : (int, int) = {
  if ( T.children.isEmpty ) {
    return (0,0)
  }
  else {
    // Calculate heights and longest path lengths of children
    recursive = T.children.map { c => helper(c) }
    heights = recursive.map { p => p[1] }
    paths = recursive.map { p => p[2] }

    // Find the two largest subtree heights
    height1 = heights.max
    if (heights.length == 1) {
      height2 = -1
    } else {
      height2 = (heights.remove(height1)).max
    }

    // Determine length of longest path (see above)        
    longest = max(paths.max, height1 + height2 + 2)

    return (height1 + 1, longest)
  }
}

  1. A(k) является наименьшим значением в (статистика заказа).kA
Рафаэль
источник
@JeffE Относительно второго комментария: Действительно, и об этом позаботятся в последнем ряду: height1 + height2это длина этого пути. Если это действительно самый длинный путь, его выбирает max. Это также объясняется в тексте выше, так что я не совсем понимаю вашу проблему? Конечно, вы должны выполнить повторение, чтобы выяснить, действительно ли это самый длинный путь, и даже если нет, это не помешает (относительно правильности) повторения.
Рафаэль
@JeffE Что касается первого комментария, вычисление для height2явно снимает height1с рассмотрения, так как же он может выбрать одного и того же потомка дважды? Это также было объяснено во вступительном тексте.
Рафаэль
1
По-видимому, мы говорим на разных диалектах псевдокодов, потому что мне трудно понять ваш. Было бы полезно добавить явное объявление на английском языке, которое longestPathHeight(T)возвращает пару (h,d), где hвысота Tи dдиаметр T. (Верно?)
Джефф
@JeffE Верно; Я думал, что это было ясно из кода, учитывая объяснение, но, по-видимому, моя экстраполяция «clear» для других псевдокод-парадигм была недостаточной (я полагаю, это Scalaesque, я думаю). Извините за путаницу, я уточняю код (надеюсь).
Рафаэль
8

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

Вот краткое изложение того, что я хочу объяснить в моем блоге :

Рекурсивный подход - диаметр дерева. Другой способ решения этой проблемы заключается в следующем. Как мы уже упоминали выше, диаметр может

  1. полностью лежать в левом поддереве или
  2. полностью лежать в правом поддереве или
  3. может распространяться через корень

Это означает, что диаметр может быть идеально получен

  1. диаметр левого дерева или
  2. диаметр правильного дерева или
  3. высота левого поддерева + высота правого поддерева + 1 (1 для добавления корневого узла, когда диаметр проходит через корневой узел)

И мы знаем, что диаметр - это самый длинный путь, поэтому мы берем максимум 1 и 2 на случай, если он лежит на одной из боковых сторон, или на 3, если он проходит через корень.

Итерационный подход - диаметр дерева

У нас есть дерево, нам нужна мета-информация с каждым узлом, чтобы каждый узел знал следующее:

  1. Высота его левого ребенка,
  2. Высота его правого ребенка и
  3. Самое дальнее расстояние между его листовыми узлами.

Как только у каждого узла есть эта информация, нам нужна временная переменная для отслеживания максимального пути. Ко времени завершения алгоритма у нас есть значение диаметра в переменной temp.

Теперь нам нужно решить эту проблему восходящим подходом, потому что мы понятия не имеем о трех значениях для корня. Но мы знаем эти значения для листьев.

Шаги для решения

  1. Инициализируйте все листья с leftHeight и rightHeight как 1.
  2. Инициализируем все листья с maxDistance как 0, мы отмечаем, что если значение leftHeight или rightHeight равно 1, то maxDistance = 0
  3. Двигайтесь вверх по одному за раз и вычислите значения для ближайшего родителя. Это было бы легко, потому что теперь мы знаем эти ценности для детей.
  4. В данном узле

    • присвойте leftHeight максимальное значение (leftHeight или rightHeight его левого дочернего элемента).
    • присвойте rightHeight максимальное значение (leftHeight или rightHeight его правого потомка).
    • если любое из этих значений (leftHeight или rightHeight) равно 1, то maxDistance будет равно нулю.
    • если оба значения больше нуля, присвойте maxDistance значение leftHeight + rightHeight - 1
  5. Сохраните значение maxDistance в переменной temp, и если на шаге 4 значение maxDistance больше текущего значения переменной, замените его новым значением maxDistance.
  6. В конце алгоритма значением в maxDistance является диаметр.
дхарам
источник
1
Что это добавляет к моему старому ответу, кроме того, что он менее общий (вы имеете дело только с бинарными деревьями)?
Рафаэль
9
Этот ответ более читабелен и понятен на мой взгляд (ваш псевдокод очень запутанный).
reggaeguitar
-3

Ниже приведен код, который возвращает путь диаметра, используя только один обход DFS. Требуется дополнительное пространство для отслеживания наилучшего видимого диаметра, а также самого длинного пути, начинающегося в конкретном узле дерева. Это подход динамического программирования, основанный на том факте, что путь с самым длинным диаметром либо не содержит корня, либо является комбинацией двух самых длинных путей соседей корня. Таким образом, нам нужно два вектора, чтобы отслеживать эту информацию.

 int getDiam(int root, vector<vector<int>>& adj_list, int& height, vector<int>& path, vector<int>& diam) {
    visited[root] = true;
    int m1 = -1;
    int m2 = -1;
    int max_diam = -1;
    vector<int> best1 = vector<int>();
    vector<int> best2 = vector<int>();
    vector<int> diam_path = vector<int>();
    for(auto n : adj_list[root]) {
        if(!visited[n]) {
            visited[n] = true;
            int _height = 0;
            vector<int> path1;
            vector<int> path2;
            int _diam = getDiam(n, adj_list, _height, path1, path2);
            if(_diam > max_diam) {
                max_diam = _diam;
                diam_path = path2;
            }
            if(_height > m1) {
                m2 = m1;
                m1 = _height;
                best2 = best1;
                best1 = path1;
            }
            else if(_height > m2) {
                m2 = _height;
                best2 = path1;
            }
        }
    }

    height = m1 + 1;

    path.insert( path.end(), best1.begin(), best1.end() );
    path.push_back(root);

    if(m1 + m2 + 2 > max_diam) {
        diam = path;
        std::reverse(best2.begin(), best2.end());
        diam.insert( diam.end(), best2.begin(), best2.end() );
    }
    else{
        diam = diam_path;
    }


    return max(m1 + m2 + 2, max_diam);
}
Тревор Ван Лоон
источник
2
Это не сайт кодирования. Мы не одобряем ответы, которые состоят в основном из блока кода. Вместо этого нам нужны ответы, которые объясняют идеи, лежащие в основе алгоритма, и дают краткий псевдокод (который не требует знания какого-либо конкретного языка программирования для понимания). Как вычислить самый длинный путь, начинающийся с определенного узла в дереве? (особенно потому, что самый длинный путь может начинаться с «восходящего» дерева DFS, т. е. обратно к корню)
DW