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

Für jeden Knoten v: visited(v) = false, finished(v) = false
Für jeden Knoten v:
  DFS(v)

DFS(v):
  if finished(v)
    return
  if visited(v)
    "Zyklus gefunden" und Abbruch
  visited(v) = true
  für jeden Nachfolger w
    DFS(w)
  finished(v) = true