Ein Zyklus (auch Kreis oder Zyklus im Graphen) ist ein Pfad, der an einem Knoten beginnt und endet, ohne dabei eine Kante mehrfach zu benutzen. Ein Graph ohne Zyklen heißt azyklisch.
Warum Zyklen wichtig sind
Zyklen sind in vielen Anwendungen unerwünscht: Abhängigkeitsgraphen, Netzwerk-Routen oder Build-Prozesse dürfen sich nicht im Kreis drehen. Ein Baum ist per Definition ein zyklenfreier Graph — jede zusätzliche Kante in einem Baum erzeugt genau einen Zyklus.
Zyklus-Erkennung
Die Tiefensuche erkennt Zyklen, indem sie eine Rückwärtskante zu einem noch offenen Knoten im Suchpfad findet. Der Union-Find-Algorithmus eignet sich ebenfalls: Fügt man eine Kante hinzu, deren beide Enden bereits in derselben Menge liegen, entsteht ein Zyklus. Genau diese Regel nutzt der Kruskal-Algorithmus für den minimalen Spannbaum.
Gerichtete azyklische Graphen
Ein gerichteter Graph ohne Zyklen heißt DAG (Directed Acyclic Graph). Nur in einem DAG ist eine topologische Sortierung möglich — etwa für Build-Reihenfolgen oder Aufgabenplanung.
Zyklen in Bäumen
Da ein Binärbaum eine Baumform ist, enthält er niemals Zyklen. Blätter sind Knoten ohne ausgehende Kanten, und jede Suche endet in endlicher Zeit — die Grundlage fast aller Traversierungs-Verfahren.