Hallo,

ich versuche momentan gerade, in einem (gerichteten) Graphen die Kreise zu finden.

Momentan ist mein Ansatz der, dass ich rekursiv Knoten aus dem Graph entferne und überprüfe, ob der resultierende Teilgraph ein Kreis ist. Die Überprüfung der Kreiseigenschaft nehme ich durch eine beschränkte Tiefensuche vor, die durch n = Anzahl der Knoten im Graph beschränkt ist. Wenn der Walker nach n+1 Schritten alle Knoten besucht hat und wieder beim Ursprung ankommt, dann ist ein Kreis gefunden.

Dabei gibt es zwei Probleme:

• Zum einen hat ein Graph mit n Knoten 2^n Teilgraphen (wenn man die Kanten außer Acht lässt), was zunächst sehr viel ist. Man kann es dadurch verringern, dass bei einem Teilgraph, der ein Kreis ist, die Rekursion nicht weiter betrachtet werden muss (das ist sinnvoll, wenn man nicht alle Kreise, sondern nur die größtmöglichen finden will). Das ändert aber nichts am worst-case-Verhalten.
  
• Zum anderen ist das Überprüfen, ob ein Graph ein Hamiltonkreis ist, bekanntermaßen ein NP-vollständiges Problem. D.h., die Frage lässt sich auch nicht in polynomieller Laufzeit lösen.

Habt ihr irgendwelche Ideen, wie man effizient Kreise in einem Graphen finden kann? Kennt ihr irgendwelche Algorithmen?

Ich bin jetzt noch mal anders herangegangen:

Alle n Knoten werden in einer durch n beschränkten Tiefensuche durchschritten. Wichtig ist festzustellen, ob dabei ein Kreis gefunden wurde. Rückgabewert ist aber nicht der Kreis, sondern der längste Pfad, der innerhalb der Tiefensuche gefunden wurde (sonst würde evtl. ein recht kurzer Kreis zurückgegeben werden).

Im zweiten Schritt werden dann die Tiefensuchen noch einmal betrachtet, in denen ein Kreis gefunden wurde. Die Pfade werden vom letzten Knoten ausgehend daraufhin untersucht, ob ein Pfad zum ersten Knoten des Pfads, also ein Kreis, existiert. Wenn ja, dann haben wir einen Kreis gefunden und können ihn speichern. Wenn nein, dann wird der letzte Knoten des Pfads gelöscht und der vorletzte betrachtet usw.

Nun hat man eine Menge an Kreisen, die man noch daraufhin untersuchen muss, ob einige Kreise von anderen überlagert werden.

Dieser Algorithmus ist zumindest etwas stack-freundlicher als der vorherige und terminiert auf jeden Fall. Allerdings ist er noch zu langsam. Schon für Graphen mit n > 20 Knoten kann es leicht 5 Minuten dauern, bis die Kreise gefunden wurden. Interessanterweise ist dabei der erste Schritt, die n-fache Tiefensuche, schon sehr rechenlastig. Ich hätte gedacht, dass eher der zweite Schritt der rechenlastige ist, weil hier für k Pfade der (Durchschnitts-)Länge l k*l Tiefensuchen durchgeführt werden.

Wie kommt das? In der beschränkten Tiefensuche ist die Rekursionstiefe maximal n, und ein Knoten hat maximal n-1 Nachbarn, somit wird die Schleife in einem Methodenaufruf auch maximal n-1-mal durchlaufen. Das führt doch zu einer Komplexität von O(n * (n-1)) = O(n^2), oder? Die Tiefensuche wird n-mal ausgeführt, also O(n * n^2) = O(n^3). Das sollte doch relativ schnell erledigt sein. Dauer aber irgendwie sehr lange.

Hier mal der Quelltext für den Walker bei der Tiefensuche im ersten Schritt, falls es jemanden interessiert. Die Methode getHeads() gibt die Nachfolger eines Knotens zurück. pointsTo(GraphNode node) ermittelt, ob ein Knoten einen Nachfolger node hat oder nicht. Beim ersten Aufruf von buildWalker() ist step = 0 und visitedList enthält genau einen Knoten.