Wie Suche ich in einem möglichst langen weg in einem Graphen

[marabu]

Hi Pelzi,

mir kommt da noch folgender Algorithmus in den Sinn: Du bestimmtst die konvexe Hülle der Knotenmenge und verbindest dann die einzelnen Knoten im Uhrzeigersinn, wobei du sie gleichzeitig aus der betrachteten Knotenmenge entfernst. Die Verbindung des letzten Knoten mit dem ersten Knoten unterlässt du dann und bildest für die Restmenge wieder die konvexe Hülle. Den letzten Knoten der ersten Hülle verbindest du mit dem nächstgelegenen der zweiten Hülle und so weiter. Bildlich entsteht soetwas wie eine Schnecke.

Frohe Weihnachten