Zyklenerkennung im Graphen

Pseudocode

Gerichtete und ungerichtete Graphen brauchen wirklich verschiedene Tests. Die gerichtete Variante verfolgt den Rekursionsstapel, die ungerichtete den Vorgänger.

// Gerichtet: DFS mit drei Farben
WEISS = unbesucht, GRAU = im Stapel, SCHWARZ = fertig

hatZyklus(u):
    farbe[u] = GRAU
    für jeden Nachbarn v von u:
        wenn farbe[v] == GRAU: gib wahr zurück
        wenn farbe[v] == WEISS und hatZyklus(v):
            gib wahr zurück
    farbe[u] = SCHWARZ
    gib falsch zurück

// Ungerichtet: DFS, die den Vorgänger mitführt
hatZyklus(u, vorgänger):
    besucht.hinzufügen(u)
    für jeden Nachbarn v von u:
        wenn v == vorgänger: weiter
        wenn v in besucht: gib wahr zurück
        wenn hatZyklus(v, u): gib wahr zurück
    gib falsch zurück

Der Unterschied wiegt schwerer, als er aussieht. In einem gerichteten Graphen ist das Erreichen eines SCHWARZEN Knotens eine Querkante und völlig zyklenfrei, sodass die naive Besuchtprüfung Zyklen meldet, die es nicht gibt. In einem ungerichteten Graphen verhindert das Überspringen des Vorgängers, dass jede einzelne Kante als Zweiknotenzyklus gelesen wird.

Durchgerechnetes Beispiel, Schritt für Schritt

Führe den gerichteten Dreifarbentest auf einem Graphen aus, der einen Zyklus und eine irreführende Querkante enthält.

Beispielgraph: Gerichtete Kanten A nach B, A nach C, B nach D, C nach D und D nach B.

1. A betreten. farbe[A] = GRAU. Nimm den ersten Nachbarn, B.
2. B betreten. farbe[B] = GRAU. Sein einziger Nachbar ist D.
3. D betreten. farbe[D] = GRAU. Sein Nachbar ist B, und farbe[B] ist GRAU. B liegt im aktuellen Rekursionsstapel, also ist D nach B eine Rückkante und der Zyklus B nach D nach B ist bestätigt.
4. Was die naive Variante täte. Angenommen, die Kante D nach B fehlte. D würde SCHWARZ abschließen, die Kontrolle liefe zurück zu A, und A nach C nach D fände D bereits besucht. Eine einfache Besuchtprüfung nennte das einen Zyklus. Das ist keiner: es ist eine Querkante in einen abgeschlossenen Teilbaum, und der Dreifarbentest ignoriert sie korrekt, weil D SCHWARZ ist und nicht GRAU.

Der Graph enthält tatsächlich einen Zyklus, B nach D nach B, gefunden über den GRAU-Test. Der Weg A nach C nach D ist kein Zyklus, und nur die Farbunterscheidung trennt die beiden Fälle.

Komplexität und woher sie kommt

Zeit: O(V + E) · Speicher: O(V)

Beide Varianten sind eine einzelne DFS mit konstantem Zusatzaufwand je Kante, die Kosten entsprechen also denen des Durchlaufs. Das Farbfeld beziehungsweise die Besuchtmenge ist O(V), dazu O(V) Rekursionsstapel. Die Union-Find-Alternative für ungerichtete Graphen läuft in O(E alpha(V)), praktisch linear, und ist vorzuziehen, wenn die Kanten einzeln eintreffen und du die zyklusschließende Kante direkt beim Einfügen ablehnen willst, ohne den Graphen erneut zu durchlaufen.

Wann Zykluserkennung passt und wann nicht

Wähle den Test passend zur Richtung deiner Kanten und dazu, ob der Graph statisch ist oder nach und nach entsteht.

Häufige Fehler

• Den ungerichteten Test auf einem gerichteten Graphen verwenden. Das ist der mit Abstand häufigste Fehler bei der Zyklenerkennung. Eine einfache Besuchtprüfung meldet auf einem gerichteten Graphen für jede Querkante in einen bereits abgeschlossenen Teilbaum einen Zyklus. Nutze drei Farben oder führe den Rekursionsstapel als eigene Menge.
• Die Markierung des Rekursionsstapels nicht zurücksetzen. Die Markierung GRAU muss beim Abschluss des Knotens auf SCHWARZ wechseln. Bleiben Knoten GRAU, sieht jeder spätere Weg dorthin wie eine Rückkante aus, was ab der zweiten DFS-Wurzel falsche Treffer erzeugt.
• Bei unzusammenhängenden Komponenten nicht neu starten. Eine DFS von einer Quelle sieht nur eine Komponente. Der Zyklus kann in einer Komponente liegen, die du nie betreten hast, also iteriere über alle Knoten und starte von jedem noch unbesuchten eine neue DFS.
• Schleifen und Mehrfachkanten. Eine Schleife auf sich selbst ist ein Zyklus der Länge eins, den die Vorgängerprüfung nicht erkennt. Zwei parallele Kanten zwischen demselben Paar bilden in einem ungerichteten Multigraphen einen Zyklus der Länge zwei, doch bedingungsloses Überspringen des Vorgängers verdeckt ihn. Überspringe die Vorgängerkante einmal, nicht bei jedem Auftreten.

Häufig gestellte Fragen

Wie erkennt man einen Zyklus in einem gerichteten Graphen?

Führe eine DFS aus, die Knoten weiß, grau und schwarz färbt. Ein Knoten ist grau, solange er im aktuellen Rekursionsstapel liegt, und schwarz, sobald er abgeschlossen ist. Eine Kante zu einem grauen Knoten ist eine Rückkante und beweist einen Zyklus. Eine Kante zu einem schwarzen Knoten ist eine Quer- oder Vorwärtskante und beweist nichts. Der gesamte Test ist O(V + E).

Wie erkennt man einen Zyklus in einem ungerichteten Graphen?

Führe eine DFS aus, die den Vorgänger jedes Knotens mitführt. Erreichst du einen bereits besuchten Knoten, der nicht der Vorgänger ist, schließt diese Kante einen Zyklus. Alternativ nutze Union-Find: verarbeite die Kanten einzeln und melde einen Zyklus, sobald beide Endpunkte bereits in derselben Menge liegen.

Warum versagt die Besuchtprüfung bei gerichteten Graphen?

Weil besucht nur bedeutet, dass der Knoten früher erreicht wurde, nicht dass er ein Vorfahre des aktuellen Knotens ist. Im Graphen A nach B, A nach C, B nach D, C nach D gibt es keinen Zyklus, dennoch markiert eine einfache Besuchtprüfung die Kante C nach D, weil D bereits über B gesehen wurde. Du musst wissen, ob das Ziel noch im Rekursionsstapel liegt.

Was ist der schnellste Weg, einen Zyklus zu erkennen?

Für einen statischen Graphen ist eine einzelne DFS mit O(V + E) optimal, da man die Eingabe mindestens lesen muss. Für einen ungerichteten Graphen, der Kante für Kante entsteht, ist Union-Find in der Praxis besser, weil jede hinzugefügte Kante in nahezu konstanter Zeit geprüft wird, ohne erneut zu durchlaufen.

Kann ein DAG einen Zyklus enthalten?

Nein, per Definition. Ein gerichteter azyklischer Graph ist genau ein gerichteter Graph ohne Zyklen, und deshalb ist die Zyklenerkennung die übliche Gültigkeitsprüfung vor der topologischen Sortierung. Existiert ein Zyklus, existiert keine gültige topologische Ordnung.