Zyklen in gerichteten Graphen erkennen
Färben Sie Knoten, um Rückkanten zu finden
Zyklen in gerichteten Graphen erkennen ist eine kostenlose Competitive Programming Academy-Lektion auf CoddyKit. Dies ist Lektion 2 von 4. Du kannst die komplette Lektion unten kostenlos lesen – dann übst du sie direkt im Browser mit einem integrierten Code-Editor und einem KI-Tutor rund um die Uhr. Sie ist Teil des Competitive Programming Academy-Lernpfads, und dein Fortschritt wird über Web und CoddyKit-App synchronisiert. Der Competitive Programming Academy-Kurs umfasst insgesamt 4 Lektionen.
Warum Zyklen wichtig sind
Ein gerichteter Zyklus bedeutet, dass Abhängigkeiten auf sich selbst zurückverweisen. Wenn Sie einen solchen Zyklus erkennen, wissen Sie, dass keine topologische Reihenfolge und kein gültiger Ablaufplan existieren kann.
Ungerichtete Graphen sind anders
Bei der Zykluserkennung kommt es hier auf die Richtung an. Kanten in die falsche Richtung zu verfolgen zählt nicht, daher lassen sich Tricks für ungerichtete Graphen nicht anwenden.
Die Idee mit drei Farben
Geben Sie jedem Knoten eine von drei Farben: Weiß bedeutet noch nicht besucht, Grau bedeutet in Bearbeitung und Schwarz bedeutet vollständig verarbeitet.
WHITE, GRAY, BLACK = 0, 1, 2
color = [WHITE] * nGrau bedeutet auf dem Stack
Ein grauer Knoten befindet sich auf Ihrem aktuellen DFS-Pfad. Sie haben ihn betreten, aber noch nicht alle seine Nachfolger vollständig untersucht.
Einen Knoten betreten
Wenn DFS einen Knoten erreicht, markieren Sie ihn vor der Untersuchung mit Grau. Dadurch kennzeichnen Sie ihn als Teil des aktiven Pfads.
def dfs(u):
color[u] = GRAYDas Signal der Rückwärtskante
Wenn Sie einen Nachbarn erreichen, der bereits grau ist, haben Sie eine Rückwärtskante in den aktuellen Pfad gefunden. Das ist ein Zyklus.
for v in adj[u]:
if color[v] == GRAY:
return True # cycleIn weiße Knoten rekursiv absteigen
Ein weißer Nachbar wurde noch nicht besucht, also steigen Sie rekursiv in ihn ab. Geben Sie sofort True nach oben zurück, sobald ein tieferer Aufruf einen Zyklus meldet.
elif color[v] == WHITE and dfs(v):
return TrueSchwarz bedeutet sicher
Ein schwarzer Nachbar wurde vollständig untersucht und enthält keinen Zyklus, daher können Sie ihn ignorieren. Ihn erneut zu besuchen würde nur Zeit kosten.
Einen Knoten abschließen
Nachdem alle Nachbarn verarbeitet wurden, markieren Sie den Knoten mit Schwarz. Er verlässt den aktiven Pfad und gilt als abgeschlossen.
color[u] = BLACK
return FalseJede Zusammenhangskomponente abdecken
Der Graph kann nicht zusammenhängend sein. Starten Sie daher DFS von jedem noch weißen Knoten, damit Sie den gesamten Graphen überprüfen.
if any(color[u]==WHITE and dfs(u) for u in range(n)):
print('cycle')Die Rekursionsgrenze beachten
Tiefe Graphen können den Rekursionsstack von Python zum Überlaufen bringen. Erhöhen Sie das Limit oder schreiben Sie DFS mit einem expliziten Stack um.
import sys
sys.setrecursionlimit(300000)Schnelltest
Während DFS erreichen Sie einen Nachbarn, der momentan grau ist. Was haben Sie gerade gefunden?
Rückblick: Zykluserkennung
Färben Sie Knoten weiß, grau und anschließend schwarz. Ein grauer Nachbar während DFS ist eine Rückwärtskante und beweist einen gerichteten Zyklus. 🔁
Häufig gestellte Fragen
Ist die Lektion „Zyklen in gerichteten Graphen erkennen“ kostenlos?
Ja — der vollständige Text von „Zyklen in gerichteten Graphen erkennen“ ist hier im Web kostenlos zu lesen. Um sie interaktiv zu üben (integrierter Code-Editor und 24/7 KI-Tutor) und den Rest des Competitive Programming Academy-Kurses freizuschalten, upgrade auf CoddyKit PRO. Der Competitive Programming Academy-Kurs umfasst insgesamt 4 Lektionen.
Was lerne ich in „Zyklen in gerichteten Graphen erkennen“?
Färben Sie Knoten, um Rückkanten zu finden Du übst Competitive Programming Academy mit praktischem Code, den du direkt im Browser ausführst, und ein 24/7 KI-Tutor beantwortet deine Fragen während du die Lektion bearbeitest.
Brauche ich Erfahrung, um Competitive Programming Academy zu starten?
Keine Vorkenntnisse erforderlich. Competitive Programming Academy auf CoddyKit ist für Anfänger bis fortgeschrittene Lernende strukturiert, sodass du hier starten oder von Anfang an beginnen und in deinem eigenen Tempo voranschreiten kannst. Dies ist Lektion 2 von 4.
Wie lange dauert die Lektion „Zyklen in gerichteten Graphen erkennen“?
Die meisten CoddyKit-Lektionen dauern etwa 5–10 Minuten. Jede ist kompakt und interaktiv, sodass du stetig Fortschritte machst und genau dort weitermachst, wo du aufgehört hast – im Web und in der App.
Kann ich in dieser Competitive Programming Academy-Lektion Code schreiben und ausführen?
Ja. Jede Competitive Programming Academy-Lektion enthält einen integrierten Code-Editor, sodass du echten Code direkt in deinem Browser schreibst und ausführst und sofort KI-Feedback erhältst — ohne lokale Einrichtung erforderlich.
Alle Lektionen in diesem Kurs
- Topologische Sortierung mit Kahns Algorithmus
- Zyklen in gerichteten Graphen erkennen
- Stark zusammenhängende Komponenten
- Brücken und Artikulationspunkte