Ich habe einen Baum (im Sinne der Graphentheorie), wie das folgende Beispiel:
Dies ist ein gerichteter Baum mit einem Startknoten (der Wurzel) und vielen Endknoten (den Blättern). Jeder Kante ist eine Länge zugeordnet.
Meine Frage ist, wie man den längsten Weg findet, der an der Wurzel beginnt und an einem der Blätter endet. Der Brute-Force-Ansatz besteht darin, alle Wurzelblattpfade zu überprüfen und den Pfad mit der maximalen Länge zu verwenden. Ich würde jedoch einen effizienteren Algorithmus bevorzugen, wenn es einen gibt.
algorithms
graphs
Graviton
quelle
quelle
Antworten:
Ran G. gab Hinweise auf einen effizienten Algorithmus, ließ aber vielleicht einige Details aus. Das Berechnen aller Wurzelblattpfade ist in der Tat ein wenig ineffizient, wenn Sie immer wieder arbeiten, z. B. wenn Sie jeden Pfad berechnen und dann die Länge berechnen.
Führen Sie den folgenden rekursiven Algorithmus aus, der mit
LongestPath(root)
dem gewünschten Ergebnis beginnt . Im Wesentlichen berechnet es rekursiv den längsten Pfad für jeden Unterbaum. Dazu müssen an jedem Knoten die neuen Pfade erstellt und der längste zurückgegeben werden.Dies ist eine Kombination aus Pseudo-Code und einer Haskell-Notation, daher hoffe ich, dass dies verständlich ist.
quelle