Zyklus (Graphentheorie)

Ein Zyklus oder Kreis ist in der Graphentheorie eine Folge verschiedener Kanten, deren Start- und Endknoten identisch ist.

Der zyklische Teilgraph kann dann durch die Abfolge der Knoten dargestellt werden, die beim „Ablaufen“ besucht werden: $(v_0, v_1, v_2, \ldots , v_n, v_0)$

Die Frage, ob und unter welchen Bedingungen eine solche Kantenfolge existiert, wird in der Graphentheorie untersucht. Ein Algorithmus hierfür ist eine modifizierte Topologische Sortierung oder eine modifizierte Tiefensuche.

Für weitere Informationen siehe auch Wege, Pfade, Zyklen und Kreise in Graphen

Zykluserkennung mittels Tiefensuche

1. Für jeden Knoten v: visited(v) = false, finished(v) = false
2. Für jeden Knoten v:
   • DFS(v)

DFS(v):

1. if finished(v)
   • return
2. if visited(v)
   • "Zyklus gefunden" und Abbruch
3. visited(v) = true
4. für jeden Nachfolger w
   • DFS(w)
5. finished(v) = true