Finden Sie die einfachen Zyklen in einem gerichteten Diagramm

15

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: Bildbeschreibung hier eingeben

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!. Bildbeschreibung hier eingeben

Hier ist meine Anzahl von einfachen Schleifen für mein Fallproblem.

Bildbeschreibung hier eingeben Bildbeschreibung hier eingebenBildbeschreibung hier eingeben Bildbeschreibung hier eingeben Bildbeschreibung hier eingeben Bildbeschreibung hier eingeben

Jonaprieto
quelle
Ich fand diese stackoverflow.com/questions/2939877/…
jonaprieto

Antworten:

13

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

Abstrakt. Ein Algorithmus vorgestellt , das durch begrenzte alle Elementarschaltungen-eines gerichteten Graphen in der Zeit fest , O((n + e)(c + 1))und Raum , der durch begrenzt O(n + e), wo es nEckpunkten, eKanten und cElementarschaltungen in der grafischen Darstellung. Der Algorithmus ähnelt den Algorithmen von Tiernan und Tarjan, ist jedoch schneller, da er jede Flanke höchstens zweimal zwischen einer Schaltung und der nächsten in der Ausgabesequenz berücksichtigt.

Das Papier enthält einen vollständigen Algorithmus.

Badroit
quelle
In Ordnung. Das Papier ist perfekt, aber kann ich mit meiner Arbeit irgendwohin gehen oder nur das Papier anschauen? Ich habe gesucht, um Ihnen die Lösung vorzustellen. Was vergesse ich bei meiner Idee?
Jonaprieto
2
Ihr Hauptproblem ist, dass der DFS-Baum nicht eindeutig ist (z. B. tauschen Sie "1" mit "3" in Ihrem Diagramm). Sie müssten sich alle möglichen DFS-Bäume ansehen, um alle Zyklen aufzulisten.
Badroit
1
Falls Sie eine Java-Implementierung dieses Algorithmus benötigen: github.com/1123/johnson
user152468
@ Badroit Link ist kaputt ... :(
Jorge E. Hernández
@ lalongooo, danke ja, ich habe es ersetzt.
Badroit