Dieses Problem sieht für mich sehr interessant aus. Es sollte ein einfacher Zyklus (dh ein Zyklus, in dem keine Wiederholungsknoten vorhanden sind) in einem gerichteten Graphen gefunden werden.
Meine Lösung sieht so aus, dh diese Grafik ist ein Fallproblem:
Ich weiß, dass es einen Zyklus in einem Graphen gibt, in dem Sie "Hinterkanten" in einer Tiefensuche finden können (gestrichelt in meinem Bild in DFSTree), und für einen Moment kann ich sicher ein paar Zyklen, aber nicht für Alles einfache Zyklen. Denn die gerichteten egdes so wichtig aus einem Zyklus, dh (0123)! = (0321)
Ich überlege, für jeden Knoten mit Hinterkanten ein DFS zu erstellen, bin mir aber nicht sicher und es ist nicht klar. Also frage ich dich, ob du mich führst. Vielen Dank!.
Hier ist meine Anzahl von einfachen Schleifen für mein Fallproblem.
quelle
Antworten:
Diese Frage scheint sehr Googleable zu sein. Möglicherweise interessieren Sie sich für den in diesem Artikel vorgestellten Algorithmus:
Finden aller Elementarkreise eines gerichteten Graphen . Donald B. Johnson. SIAM J. COMPUT. Vol. 1, März 1975
Das Papier enthält einen vollständigen Algorithmus.
quelle