17. Aug 2008, 12:59

Als Zyklus, Kreis oder geschlossene Kantenfolge bezeichnet man in der Graphentheorie eine Kantenfolge, deren Start- und Endknoten identisch sind.

Der zyklische Teilgraph kann dann durch die Abfolge der Knoten dargestellt werden, die beim "Ablaufen" besucht werden:

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

[Bearbeiten] 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

Dieser Artikel ist eine Kopie aus der freien Enzyklopädie Wikipedia. Am Originalartikel kann jeder Korrekturen und Ergänzungen vornehmen. Zudem kann man frühere Versionen einsehen.

Abkürzungen • Dateiendungen • Netzjargon