Es soll als Beispiel folgender http://www.muecke99.de/tmp/graph-pfadsuche.jpg gerichteter, zyklischer Graph gegeben sein.
Frage: Wie kann ich alle Pfade in diesem Graphen finden, dabei sollen Zyklen besucht werden.
Gibt es dazu einen Algorithmus, mit dem ich alle Pfade eines Graphen finden kann? Wie kann ich Abbruchbedingungen für die Zyklen bestimmen? Wäre supi, wenn mir jemand weiterhelfen könnte.
Gruss muecke99
Du weisst natuerlich, dass es expmnentiell viele Pfade in einem Graphen gibt ?!?
Alle Pfade finden kannst Du natürlich einfach durch Backtracking, z.B. diurch eine rekursive Schleife, die in jedem Schritt einen npch nicht besuchten Knoten auswählt.
Was die Zyklen angeht: eine minimale Kantenmenge zu finden, die alle Zyklen trifft ist NP-hart.
Als heuristisches Branching-Kriterium für Backtracking würe ich jeder Kante, die auf einem Zykklus liegt, einen solchen zuordnen und immer überprüfen, ob dieser
vom gegebenen Suchpunkt aus noch erreichbar ist. Wird dieser zyklus getroffen, aber die kante nicht, so wird für die Kante ein neuer (ungetroffener) Zyklus gewählt entweder durch Neuberechnen (bis zu O(m)) oder durtch verwenden eines
sonstwo in der Suche gefundenen Zyklus (Speicherplatz !!).
Heuristische ideen gibt es da aber vermutlich viele.
MfG
ML
[Bei dieser Antwort wurde das Vollzitat nachträglich automatisiert entfernt]
