Graphenverarbeitung

[3_of_8]

Morgen,

ich habe gerade ein Problem, einen Algorithmus zu finden. Ich habe einen zusammenhängenden, ungerichteten Graphen. Ich würde jetzt gerne alle Zyklen in diesem Graphen finden und die dazugehörigen Knoten irgendwie markieren. Wenn ich die markierten Knoten jetzt entferne, habe ich entweder gar nichts mehr oder einen oder mehrere nichtzyklische Graphen.

Ich nehme mir jetzt einen beliebigen solchen Graphen. Dann ist dieser Graph praktisch eine (möglicherweise verzweigte) Kette. Aus diesem Graphen würde ich jetzt gerne die längste Kette auswählen.

Wie kann ich das halbwegs effizient realisieren? Beim ersten Teilproblem habe ich mir überlegt, einfach einen Knoten auszuwählen und per Tiefensuche durchzugehen, wobei ich jeden besuchten Knoten markiere, und wenn ich bei der Suche auf einen schon markierten Knoten stoße, dann habe ich einen Zyklus gefunden. Wenn ich außerdem noch eine aufsteigende Nummerierung verwende, müsste ich auch in der Lage sein, zu bestimmen, wie viele Knoten der Zyklus lang ist.

Beim zweiten Problem aber fällt mir außer Bruteforcing kein Ansatz ein, der alle Fälle abdeckt.