Gibt es einen effizienten Algorithmus zur Erkennung von Zyklen innerhalb eines gerichteten Graphen?
Ich habe einen gerichteten Graphen, der einen Zeitplan von auszuführenden Aufträgen darstellt, wobei ein Auftrag ein Knoten und eine Abhängigkeit eine Kante ist. Ich muss den Fehlerfall eines Zyklus innerhalb dieses Graphen erkennen, der zu zyklischen Abhängigkeiten führt.
@kittyPL können Sie erklären, warum dieser Fall nicht eintritt? Entweder 1) Es handelt sich um einen gerichteten Graphen und daher wurde kein Zyklus gebildet oder 2) DFS würde 1 -> 2 (mit 1,2), 2 -> 3 (mit 2,3), 3 -> 1 (mit 1,3) gehen
@JakeGreene Schau mal hier: i.imgur.com/tEkM5xy.png Einfach genug, um es zu verstehen. Nehmen wir an, du startest bei 0. Dann gehst du zum Knoten 1, von dort aus gibt es keine weiteren Pfade, die Regression geht zurück. Nun besucht man den Knoten 2, der eine Kante zum Knoten 1 hat, der bereits besucht wurde. Deiner Meinung nach hättest du dann einen Zyklus - und den hast du nicht wirklich
CodeJaeger ist eine Gemeinschaft für Programmierer, die täglich Hilfe erhalten..
Wir haben viele Inhalte, und Sie können auch Ihre eigenen Fragen stellen oder die Fragen anderer Leute lösen.
21 Stimmen
Sie sagen, Sie wollen alle Zyklen erkennen, aber Ihr Anwendungsfall legt nahe, dass es ausreichen würde, zu erkennen, ob es irgendwelche Zyklen gibt.
38 Stimmen
Es wäre besser, alle Zyklen aufzuspüren, damit sie in einem Zug behoben werden können, als zu prüfen, zu beheben, zu prüfen, zu beheben usw.
2 Stimmen
Sie sollten die Arbeit "Finding all the elementary circuits of a directed graph" von Donald B. Johnson lesen. Es werden zwar nur elementare Schaltungen gefunden, aber das sollte für Ihren Fall ausreichen. Und hier ist meine Java-Implementierung dieses Algorithmus zur Verwendung bereit: github.com/1123/johnson
0 Stimmen
Führen Sie DFS mit einer zusätzlichen Änderung für den Algorithmus aus: Markieren Sie jeden Knoten, den Sie besucht haben. Wenn Sie einen Knoten besuchen, der bereits besucht ist, haben Sie einen Cicle. Wenn Sie sich von einem Pfad zurückziehen, entfernen Sie die Markierung der besuchten Knoten.
9 Stimmen
@HeshamYassin, wenn Sie einen Knoten besuchen, den Sie bereits besucht haben, bedeutet das nicht unbedingt, dass es eine Schleife gibt. Bitte lesen Sie meinen Kommentar cs.stackexchange.com/questions/9676/ .
0 Stimmen
Ihr erster Satz widerspricht Ihrem letzten Satz; bitte korrigieren Sie ihn. Wenn Sie wirklich erkennen wollen alle die Zyklen (erster Satz), die Größe der Ausgabe und die Laufzeit sind im schlimmsten Fall exponentiell zur Größe der Eingabe. Wenn Sie wirklich nur den Fehlerfall von cualquier Zyklus (letzter Satz) können Sie das in einer Zeit tun, die linear zur Größe der Eingabe ist. Ich würde Letzteres empfehlen.
0 Stimmen
@Pneauters Nein, es wäre nicht unbedingt besser, alle Zyklen zu erkennen. Betrachten Sie den Fall, dass es eine exponentielle Anzahl von Zyklen gibt.
0 Stimmen
Sie können meine einfache und effektive Umsetzung nutzen: stackoverflow.com/a/60196714/1763149