Wie überprüfe ich einen Graph ob er einen Zyklus enthält?
-
such für das problem einen algorithmus oder was auch immer?-> gibt es da spezielle Algorithmen ?
please help
-
Jo, Du kannst ne Breitensuche machen und jeden besuchten Knoten markieren. Triffst Du unterwegs nen markierten Knoten, dann hast Du nen Zyklus gefunden. Funktioniert in dieser Form allerdings nur für ungerichtete Graphen. Alternativ kannste auch ne Tiefensuche machen... was Dir besser gefällt, Du einfacher programmieren kannst... etc.
boost::graph bietet da auch so einiges, ist allerdings wohl nicht ganz trivial zu benutzen.
MfG Jester