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

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 ′ .$v$$v'$
• 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).

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:$v$$u_1,\dots,u_k$

• Najdłuższa ścieżka w leży w jednej z poddrzew T u 1 , ... , T U K .$T_v$$T_{u_1},\dots,T_{u_k}$
• Najdłuższa ścieżka w zawiera v .$T_v$$v$

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 , $v$$H_{(k)} + H_{(k-1)} + 2$$k>1$$H_{(k)}+1$$k=1$ zbiór wielu wysokości poddrzewa¹.$H = \{ h(T_{u_i}) \mid i=1,\dots,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).$A_{(k)}$$k$$A$

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.

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);
}