Cycle Detection prüft, ob ein Graph einen Pfad enthält, der zu einem bereits aktiven Knoten zurückführt.
Das ist besonders wichtig für Dependency Graphs, Workflows, Build-Systeme und DAG-Validierung.
Gerichtete Graphen
Ein übliches DFS-Modell verwendet drei Zustände:
0 = unvisited
1 = visiting
2 = finishedEine Kante zu einem visiting-Knoten ist eine Back Edge und beweist einen Zyklus.
Ungerichtete Graphen
Hier muss der Parent berücksichtigt werden.
Ein bereits besuchter Nachbar ist nur dann ein Zyklus, wenn er nicht der Parent des aktuellen Knotens ist.
Kahn's Algorithmus
Ein gerichteter Graph ist azyklisch, wenn Kahn alle Knoten topologisch verarbeiten kann.
Bleiben Knoten übrig, existiert ein Zyklus.
Union-Find
Bei ungerichteten Graphen kann Union-Find Kanten nacheinander prüfen.
Sind beide Endpunkte bereits in derselben Menge, erzeugt die neue Kante einen Zyklus.
Anwendungen
- Circular Dependencies
- Package Graphs
- Workflow Validation
- Build-Reihenfolgen
- Kursvoraussetzungen
- Spreadsheet-Referenzen
- Service-Abhängigkeiten
Floyd
Floyd's Tortoise-and-Hare ist eher für Linked Lists oder Functional Graphs geeignet als für allgemeine Graphen.
Komplexität
DFS und Kahn:
O(V + E)Fazit
Directed und Undirected Cycle Detection benötigen unterschiedliche Logik. Das Erkennen dieser Unterscheidung ist wichtiger als das Auswendiglernen einer einzelnen Implementierung.