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 ′
- 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.
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.)
algorithms
graphs
trees
Emmy
quelle
quelle
Antworten:
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:v u1,…,uk
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¹.v H(k)+H(k−1)+2 k>1 H(k)+1 k=1 H={h(Tui)∣i=1,…,k}
Im Pseudocode sieht der Algorithmus folgendermaßen aus:
quelle
height1 + height2
ist die Länge dieses Pfades. Wenn es tatsächlich der längste Weg ist, wird er von ausgewähltmax
. 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.height2
explizitheight1
aus der Überlegung entfernt. Wie kann also dasselbe Kind zweimal ausgewählt werden? Dies wurde auch im Einführungstext erläutert.longestPathHeight(T)
die ein Paar zurückgibt(h,d)
, wobeih
die HöheT
undd
der Durchmesser von istT
. (Richtig?)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
Das bedeutet, dass der Durchmesser idealerweise von abgeleitet werden kann
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ß:
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
An einem bestimmten Knoten,
quelle
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.
quelle