Najdłuższa ścieżka w niekierowanym drzewie z tylko jednym przejściem

44

Istnieje standardowy algorytm znajdowania najdłuższej ścieżki w nieukierunkowanych drzewach przy użyciu dwóch wyszukiwań w pierwszej kolejności:

  • Uruchom DFS od losowego wierzchołka i znajdź od niego najdalszy wierzchołek; powiedzmy, że to v .vv
  • Teraz uruchom DFS od aby znaleźć wierzchołek najdalej od niego. Ta ścieżka jest najdłuższą ścieżką na wykresie.v

Pytanie brzmi, czy można to zrobić bardziej efektywnie? Czy możemy to zrobić za pomocą pojedynczego DFS lub BFS?

(Można to równoznacznie opisać jako problem obliczania średnicy drzewa bezkierunkowego).

Emmy
źródło
2
To, czego szukasz, nazywa się również średnicą drzewa. (Na drzewach „najdłuższa najkrótsza ścieżka” i „najdłuższa ścieżka” są tym samym, ponieważ istnieje tylko jedna ścieżka łącząca dowolne dwa węzły.)
Raphael

Odpowiedzi:

22

Po drodze przeprowadzamy wyszukiwanie w pierwszej kolejności i agregujemy wyniki, tzn. Rozwiązujemy problem rekurencyjnie.

Dla każdego węzła z dziećmi u 1 , , u k (w drzewie wyszukiwania) istnieją dwa przypadki:vu1,,uk

  • Najdłuższa ścieżka w leży w jednej z poddrzew T u 1 , ... , T U K .T.vT.u1,,T.uk
  • Najdłuższa ścieżka w zawiera v .T.vv

W drugim przypadku musimy połączyć jedną lub dwie najdłuższe ścieżki od do jednego z poddrzewa; są to z pewnością te do najgłębszych liści. Długość ścieżki wynosi zatem H ( k ) + H ( k - 1 ) + 2, jeśli k > 1 lub H ( k ) + 1, jeśli k = 1 , przy H = { h ( T u i ) i = 1 , vH.(k)+H.(k-1)+2)k>1H.(k)+1k=1 zbiór wielu wysokości poddrzewa¹.H.={h(T.uja)ja=1,,k}

W pseudokodzie algorytm wygląda następująco:

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. jestnajmniejszą wartością k w A (statystyka rzędu).ZA(k)kZA
Raphael
źródło
@JeffE Odnośnie do drugiego komentarza: Rzeczywiście, i to jest załatwione w ostatnim rzędzie: height1 + height2jest długość tej ścieżki. Jeśli jest to rzeczywiście najdłuższa ścieżka, wybiera ją max. Wyjaśniono to również w powyższym tekście, więc nie bardzo widzę twój problem? Na pewno musisz się powtórzyć, aby dowiedzieć się, czy rzeczywiście jest to najdłuższa ścieżka, a nawet jeśli nie, nie zaszkodzi (wrt poprawności) powtórzyć.
Raphael
@JeffE Jeśli chodzi o pierwszy komentarz, obliczenia dotyczące height2jawnie usuwa się height1z rozważań, więc jak może wybrać to samo dziecko dwa razy? Zostało to również wyjaśnione w tekście wprowadzającym.
Raphael
1
Najwyraźniej mówimy różnymi dialektami pseudokodów, ponieważ trudno mi zrozumieć twój. Pomogłoby to dodać wyraźną angielską deklarację, która longestPathHeight(T)zwraca parę (h,d), w której hwysokość Ti dśrednica to T. (Zgadza się?)
JeffE
@JeffE Right; Pomyślałem, że jest to jasne z kodu, biorąc pod uwagę wyjaśnienie, ale najwyraźniej moja ekstrapolacja „wyczyść” dla innych paradygmatów pseudokodu była niewystarczająca (chyba moja jest Scalaesque). Przepraszam za zamieszanie, wyjaśniam kod (mam nadzieję).
Raphael
8

Można to rozwiązać w lepszy sposób. Możemy również zmniejszyć złożoność czasu do O (n), wprowadzając niewielką modyfikację struktury danych i stosując podejście iteracyjne. Dla szczegółowej analizy i wielu sposobów rozwiązania tego problemu z różnymi strukturami danych.

Oto podsumowanie tego, co chcę wyjaśnić w moim blogu :

Podejście rekurencyjne - średnica drzewa Inny sposób podejścia do tego problemu jest następujący. Jak wspomniano powyżej, średnica może

  1. całkowicie leżeć w lewym sub-drzewie lub
  2. całkowicie leżeć w prawym sub-drzewie lub
  3. może obejmować cały katalog główny

Co oznacza, że ​​średnicę można idealnie wyprowadzić

  1. średnica lewego drzewa lub
  2. średnica prawego drzewa lub
  3. wysokość lewego drzewa podrzędnego + wysokość prawego drzewa podrzędnego + 1 (1, aby dodać węzeł główny, gdy średnica obejmuje cały węzeł główny)

Wiemy, że średnica jest najdłuższą ścieżką, dlatego bierzemy maksymalnie 1 i 2 w przypadku, gdy leży ona z boku lub weźmy 3, jeśli obejmuje ona rdzeń.

Podejście iteracyjne - średnica drzewa

Mamy drzewo, potrzebujemy meta informacji z każdym węzłem, aby każdy węzeł wiedział, co następuje:

  1. Wysokość jego lewego dziecka,
  2. Wysokość jego prawego dziecka i
  3. Największa odległość między węzłami liści.

Gdy każdy węzeł uzyska te informacje, potrzebujemy zmiennej tymczasowej, aby śledzić maksymalną ścieżkę. Do czasu zakończenia algorytmu mamy wartość średnicy w zmiennej temp.

Teraz musimy rozwiązać ten problem w podejściu oddolnym, ponieważ nie mamy pojęcia o trzech wartościach dla katalogu głównego. Ale znamy te wartości dla liści.

Kroki do rozwiązania

  1. Zainicjuj wszystkie liście za pomocą leftHeight i rightHeight jako 1.
  2. Zainicjuj wszystkie liście z maxDistance jako 0, sprawimy, że jeśli jeden z leftHeight lub rightHeight wynosi 1, robimy maxDistance = 0
  3. Poruszaj się w górę pojedynczo i oblicz wartości dla najbliższego rodzica. To byłoby łatwe, ponieważ teraz znamy te wartości dla dzieci.
  4. W danym węźle

    • przypisz leftHeight jako maksymalnie (leftHeight lub rightHeight jego lewego dziecka).
    • przypisz rightHeight jako maksimum (leftHeight lub rightHeight jego prawego dziecka).
    • jeśli którakolwiek z tych wartości (leftHeight lub rightHeight) wynosi 1, ustaw maxDistance na zero.
    • jeśli obie wartości są większe od zera, ustaw maxDistance jako leftHeight + rightHeight - 1
  5. Zachowaj wartość maxDistance w zmiennej temp. Jeśli w kroku 4 wartość maxDistance jest większa niż bieżąca wartość zmiennej, zastąp ją nową wartością maxDistance.
  6. Na końcu algorytmu wartością w maxDistance jest średnica.
dharam
źródło
1
Co to dodaje do mojej starszej odpowiedzi, poza tym, że jest mniej ogólne (masz do czynienia tylko z drzewami binarnymi)?
Raphael
9
Ta odpowiedź jest bardziej czytelna i łatwiejsza do zrozumienia moim zdaniem (twój pseudokod jest bardzo mylący).
reggaeguitar
-3

Poniżej znajduje się kod, który zwraca ścieżkę średnicy przy użyciu tylko jednego przejścia DFS. Wymaga dodatkowej przestrzeni, aby śledzić najlepszą dotychczas widoczną średnicę, a także najdłuższą ścieżkę rozpoczynającą się od określonego węzła w drzewie. Jest to podejście do programowania dynamicznego oparte na tym, że najdłuższa ścieżka średnicy albo nie zawiera korzenia, albo jest kombinacją dwóch najdłuższych ścieżek sąsiadów korzenia. Potrzebujemy zatem dwóch wektorów do śledzenia tych informacji.

 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);
}
Trevor Van Loon
źródło
2
To nie jest strona kodująca. Odradzamy odpowiedzi składające się głównie z bloku kodu. Zamiast tego chcemy odpowiedzi, które wyjaśniają idee algorytmu i dają zwięzły pseudokod (który nie wymaga znajomości żadnego konkretnego języka programowania do zrozumienia). Jak obliczyć najdłuższą ścieżkę rozpoczynającą się od określonego węzła w drzewie? (zwłaszcza, że ​​najdłuższa ścieżka może zacząć się od przejścia „w górę” drzewa DFS, tj. z powrotem w kierunku korzenia)
DW