Längster Pfad in einem ungerichteten Baum mit nur einer Durchquerung

44

Es gibt diesen Standardalgorithmus zum Finden des längsten Pfades in ungerichteten Bäumen unter Verwendung von zwei Tiefensuchen:

  • Starten Sie DFS von einem zufälligen Scheitelpunkt und suchen Sie den am weitesten entfernten Scheitelpunkt. sag es ist .v vv
  • Starten Sie nun ein DFS von , um den von ihm am weitesten entfernten Scheitelpunkt zu finden. Dieser Pfad ist der längste Pfad im Diagramm.v

Die Frage ist, ob dies effizienter durchgeführt werden kann. Können wir das mit einem einzelnen DFS oder BFS machen?

(Dies kann äquivalent als das Problem der Berechnung des Durchmessers eines ungerichteten Baums beschrieben werden.)

Emmy
quelle
2
Was Sie suchen, nennt man auch den Durchmesser des Baumes. (Auf Bäumen sind "längster kürzester Weg" und "längster Weg" dasselbe, da nur ein Weg zwei Knoten miteinander verbindet.)
Raphael

Antworten:

22

Wir führen eine Tiefensuche in der Nachbestellung durch und aggregieren die Ergebnisse auf dem Weg, dh wir lösen das Problem rekursiv.

Für jeden Knoten mit den Kindern (im Suchbaum) gibt es zwei Fälle:vu1,,uk

  • Der längste Pfad in liegt in einem der Unterbäume .TvTu1,,Tuk
  • Der längste Pfad in enthält .Tvv

Im zweiten Fall müssen wir den einen oder die zwei längsten Pfade von in einen der Unterbäume kombinieren . Dies sind sicherlich die tiefsten Blätter. Die Länge des Pfades ist dann wenn , oder wenn , mit der Mehrfachsatz von Teilbaumhöhen¹.vH(k)+H(k1)+2k>1H(k)+1k=1H={h(Tui)i=1,,k}

Im Pseudocode sieht der Algorithmus folgendermaßen aus:

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. k AA(k) ist der kleinste Wert in (Ordnungsstatistik).kA
Raphael
quelle
@JeffE Zum zweiten Kommentar: In der Tat, und das wird in der letzten Zeile erledigt: height1 + height2ist die Länge dieses Pfades. Wenn es tatsächlich der längste Weg ist, wird er von ausgewählt max. Es ist auch im obigen Text erklärt, also sehe ich Ihr Problem nicht ganz? Sicherlich müssen Sie sich erneut anmelden, um herauszufinden, ob es sich tatsächlich um den längsten Weg handelt, und selbst wenn dies nicht der Fall ist, tut es nicht weh, sich erneut anzumelden.
Raphael
@ JeffE In Bezug auf den ersten Kommentar wird die Berechnung für height2explizit height1aus der Überlegung entfernt. Wie kann also dasselbe Kind zweimal ausgewählt werden? Dies wurde auch im Einführungstext erläutert.
Raphael
1
Anscheinend sprechen wir verschiedene Pseudocode-Dialekte, weil ich es schwer habe, Ihre zu verstehen. Es wäre hilfreich, eine explizite englische Deklaration hinzuzufügen, longestPathHeight(T)die ein Paar zurückgibt (h,d), wobei hdie Höhe Tund dder Durchmesser von ist T. (Richtig?)
JeffE
@ JeffE Richtig; Ich dachte, das sei aus dem Code klar, wenn man die Erklärung bedenkt, aber anscheinend war meine Extrapolation von "klar" für andere Pseudocode-Paradigmen unzureichend (ich glaube, meine ist Scalaesque). Entschuldigung für die Verwirrung, ich kläre den Code (hoffentlich).
Raphael
8

Dies kann besser gelöst werden. Wir können auch die Zeitkomplexität auf O (n) reduzieren, indem wir die Datenstruktur geringfügig ändern und einen iterativen Ansatz verwenden. Für eine detaillierte Analyse und mehrere Möglichkeiten zur Lösung dieses Problems mit verschiedenen Datenstrukturen.

Hier ist eine Zusammenfassung dessen, was ich in einem Blogbeitrag von mir erklären möchte :

Rekursiver Ansatz - Baumdurchmesser Eine andere Möglichkeit, sich diesem Problem zu nähern, ist die folgende. Wie oben erwähnt kann das der Durchmesser sein

  1. ganz im linken unterbaum liegen oder
  2. ganz im rechten unterbaum liegen oder
  3. kann sich über die Wurzel erstrecken

Das bedeutet, dass der Durchmesser idealerweise von abgeleitet werden kann

  1. der Durchmesser des linken Baumes oder
  2. der Durchmesser des rechten Baumes oder
  3. die Höhe des linken Unterbaums + die Höhe des rechten Unterbaums + 1 (1, um den Wurzelknoten hinzuzufügen, wenn sich der Durchmesser über den Wurzelknoten erstreckt)

Und wir wissen, dass der Durchmesser der längste Pfad ist, also nehmen wir das Maximum von 1 und 2, falls er auf einer Seite liegt, oder wir nehmen 3, wenn er sich durch die Wurzel erstreckt.

Iterativer Ansatz - Baumdurchmesser

Wir haben einen Baum, wir brauchen eine Metainformation mit jedem Knoten, damit jeder Knoten folgendes weiß:

  1. Die Höhe seines linken Kindes,
  2. Die Höhe seines rechten Kindes und
  3. Der weiteste Abstand zwischen den Blattknoten.

Sobald jeder Knoten diese Informationen hat, benötigen wir eine temporäre Variable, um den maximalen Pfad zu verfolgen. Bis der Algorithmus beendet ist, haben wir den Wert des Durchmessers in der temporären Variablen.

Jetzt müssen wir dieses Problem in einem Bottom-up-Ansatz lösen, da wir keine Ahnung von den drei Werten für die Wurzel haben. Aber wir kennen diese Werte für die Blätter.

Schritte zu lösen

  1. Initialisiere alle Blätter mit leftHeight und rightHeight als 1.
  2. Initialisiere alle Blätter mit maxDistance als 0, wir machen es zu einem Punkt, dass wenn entweder leftHeight oder rightHeight 1 ist, wir maxDistance = 0 machen
  3. Bewegen Sie sich nacheinander nach oben und berechnen Sie die Werte für das unmittelbar übergeordnete Element. Es wäre einfach, denn jetzt kennen wir diese Werte für die Kinder.
  4. An einem bestimmten Knoten,

    • Weisen Sie leftHeight als Maximum von (leftHeight oder rightHeight des linken untergeordneten Elements) zu.
    • Weisen Sie die rechte Höhe als Maximum von (leftHeight oder rightHeight des rechten untergeordneten Elements) zu.
    • Wenn einer dieser Werte (leftHeight oder rightHeight) 1 ist, wird der maximale Abstand zu Null.
    • Wenn beide Werte größer als Null sind, geben Sie als maxDistance leftHeight + rightHeight - 1 an
  5. Behalten Sie die maxDistance in einer temporären Variablen bei. Wenn die maxDistance in Schritt 4 höher ist als der aktuelle Wert der Variablen, ersetzen Sie sie durch den neuen maxDistance-Wert.
  6. Am Ende des Algorithmus ist der Wert in maxDistance der Durchmesser.
dharam
quelle
1
Was bedeutet das für meine ältere Antwort, abgesehen davon, dass sie weniger allgemein ist (Sie beschäftigen sich nur mit Binärbäumen)?
Raphael
9
Diese Antwort ist meiner Meinung nach lesbarer und verständlicher (Ihr Pseudocode ist sehr verwirrend).
Reggaeguitar
-3

Der folgende Code gibt einen Durchmesserpfad mit nur einer DFS-Durchquerung zurück. Es ist zusätzlicher Platz erforderlich, um den besten bisher gesehenen Durchmesser sowie den längsten Pfad beginnend an einem bestimmten Knoten im Baum zu verfolgen. Dies ist ein dynamischer Programmieransatz, der auf der Tatsache basiert, dass ein Pfad mit dem längsten Durchmesser entweder keine Wurzel enthält oder eine Kombination der beiden längsten Pfade der Nachbarn der Wurzel ist. Daher benötigen wir zwei Vektoren, um diese Informationen zu verfolgen.

 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
quelle
2
Dies ist keine Codierungssite. Wir raten von Antworten ab, die hauptsächlich aus einem Codeblock bestehen. Stattdessen möchten wir Antworten, die die Ideen hinter dem Algorithmus erläutern und einen prägnanten Pseudocode angeben (für dessen Verständnis keine Kenntnisse einer bestimmten Programmiersprache erforderlich sind). Wie berechnet man den längsten Pfad, der an einem bestimmten Knoten im Baum beginnt? (Zumal der längste Pfad möglicherweise damit beginnt, den DFS-Baum "hochzugehen", dh zurück zur Wurzel)
DW