0 Daumen
117 Aufrufe

Aufgabe:

"Gegeben sei ein ungerichteter gewurzelter Baum B = (V , E) in Kind-Geschwister-Darstellung. Die Wurzel sei r.
Entwerfen Sie einen möglichst effizienten Algorithmus, welcher die Länge eines längsten einfachen Weges in B berechnet. Geben Sie Ihren Algorithmus in Pseudocode an, analysieren Sie seine Laufzeit und begründen Sie seine Korrektheit."

Ich wäre schon für den Pseudocode / Ansätze etc. sehr sehr dankbar.


Problem/Ansatz:

Ich hatte mir überlegt, ob es nicht möglich ist von jedem Knoten die Höhe zu bestimmen und dann anschließend die größten höhen zu vergleichen um dann einen einfachen Weg zu bestimmen. Aber ist dieser Algorithmus am Effizientesten und selbst wenn, weiß ich nicht ganz wie dieser in Pseudocode umzusetzen wäre.

Avatar von

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Mathelounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community