aRo
Jungspund
Dabei seit: 25.10.2007
Beiträge: 18
 |
|
| Algorithmus für maximalen Pfad gesucht |
     |
Hallo!
Vielleicht hat ja jemand mal Lust darüber nachzugrübeln.
Also gesucht ist ein Alogrithmus der in einem Baum mit positiv gewichteten Kanten die zwei Knoten sucht, die den maximalen Abstand voneinander haben und sich diesen Abstand auch merkt.
Die Laufzeit soll O(|V|) sein (V ist die Menge der Knoten).
Der Algorithmus ist zu beschreiben und begründen, muss also nicht unbedingt wirklich in einer Programmiersprache geschrieben werden.
Mein bisheriger Ansatz:
Wobei ich nicht ganz sicher bin, ob das O(|V|) ist? Was ist eig. der Unterschied zu O(V)?
Also, man muss für jeden Knoten seine 2 größten Kinder suchen. Kinder, die nicht eines der zwei größten sind, können mit eventuellem Unterbaum fallen gelassen werden (z.B. aus einer Liste gelöscht werden).
Die Werte der zwei größten Kinder und die Namen der Kinder müssen im Vater gespeichert werden.
Als Größe eines Knotens bezeichne ich die die maximal 2 Zahlen, die in ihm stehen + die verbindene Kante zum Papa.
Blätter haben also den Wert 0, mit ihnen fängt man an und aus ihnen baut man am Anfang eine Liste, aus der gestrichen wird.
Am Ende stehen die beiden gesuchten Knoten in der Wurzel und die SUmme der beiden Werte der Wurzel ist der gesuchte Abstand.
Ist das verständlich?
Was sagt ihr dazu?
|
|
