Erkennen von Zyklen in einem Graphen
Das Erkennen von Zyklen in Graphen ist von entscheidender Bedeutung, um die Struktur und Eigenschaften von Daten in unterschiedlichen Bereichen zu verstehen – zum Beispiel beim Verwalten von Abhängigkeiten, bei der Erkennung von Deadlocks oder im Bereich des Netzwerk-Routings. Wenn wir Zyklen rechtzeitig identifizieren, können wir unter anderem kreisförmige Abhängigkeiten vermeiden, Ineffizienzen reduzieren und sogar Systemausfälle verhindern.
Um einen Zyklus in einem Graphen zu erkennen, kann eine abgewandelte Version der DFS verwendet werden.
Wenn wir einen Graphen mit DFS durchlaufen, markieren wir üblicherweise Knoten als besucht oder unbesucht. Zum Erkennen von Zyklen ist das jedoch nicht ausreichend. Stattdessen benötigen wir drei Zustände für jeden Knoten:
- Knoten ist nicht besucht
- Knoten und sein zugehöriger DFS-Teilbaum werden gerade verarbeitet
- Knoten ist vollständig verarbeitet (alle Kindknoten wurden besucht)
Auf diese Weise lässt sich ein Zyklus erkennen, wenn wir bei der Durchquerung einen Knoten erreichen, der zurzeit verarbeitet wird.
➰
Wenn wir bei der Traversierung auf einen Knoten stoßen, der als "wird verarbeitet" (2) markiert ist, haben wir einen Zyklus gefunden.
Der Algorithmus führt folgende Schritte aus:
- Alle Knoten als nicht besucht markieren
- Eine DFS von einem beliebigen Knoten aus starten
- Den aktuellen Knoten als "wird verarbeitet" markieren
- Sobald alle Kindknoten des aktuellen Knotens verarbeitet sind, den Knoten als "vollständig besucht" markieren
Der Algorithmus kann sowohl bei gerichteten als auch bei ungerichteten Graphen angewendet werden:
color = [1] * n # color of vertices (1: not visited, 2: being processed, 3: fully visited)
def dfs(v, p): # depth-first search (v: vertex, p: parent)
color[v] = 2 # mark vertex as being processed
cycle = False # flag to check if there is a cycle
for to in g[v]: # for each vertex connected to v
if color[to] == 1: # if vertex is not visited
cycle |= dfs(to, v) # call dfs on vertex and mark if there is a cycle
elif color[to] == 2 and to != p: # if vertex is being processed and it is not the parent
cycle = True # mark flag as True
color[v] = 3 # mark vertex as fully visited
return cycle # return flag
for start in range(n): # for each vertex
if color[start] == 1: # if vertex is not visited
if dfs(start, -1): # call dfs on vertex and check if there is a cycle
print('Cycle') # print cycle
break # break loop
else: # If the loop wasn't stopped with break
print('No cycle') # print no cycleBeachte, dass bei gerichteten Graphen die Berücksichtigung des Elternknotens nicht notwendig ist. Weißt du warum? 🤔
Lass uns den Algorithmus an einigen Eingaben durchspielen:
n = 4, e = 4
Die Eingabe-Paare
a, b lauten: [(0, 1), (0, 2), (1, 2), (3, 2)]Der Startknoten ist 3
v=3, p=-1→color = [1, 1, 1, 2]⇒ alle Nachbarn von 3 untersuchen ⇒[2]
v=2, p=3→color = [1, 1, 2, 2]⇒ alle Nachbarn von 2 untersuchen ⇒[0, 1]
v=0, p=2→color = [2, 1, 2, 2]⇒ alle Nachbarn von 0 untersuchen ⇒[1, 2]
v=1, p=0→color = [2, 2, 2, 2]⇒ alle Nachbarn von 1 untersuchen ⇒[0, 2]⇒ 0 ist als 1 markiert ⇒cycle = True⇒return True
Herausforderung: Prüfen, ob ein Graph einen Zyklus enthält
Gegeben ist ein gerichteter Graph mit
v Knoten und e Kanten. Es soll festgestellt werden, ob der Graph einen Zyklus enthält.Eingabe
Die erste Zeile der Eingabe besteht aus zwei ganzen Zahlen
v (1 ≤ v ≤ 100 000) und e (1 ≤ e ≤ 100 000).Die folgenden
e Zeilen enthalten Paare von ganzen Zahlen v1, v2 (1 ≤ v1, v2 ≤ v). Diese Paare bedeuten, dass es einen Pfad vom Knoten v1 zum Knoten v2 gibt.Ausgabe
Das Programm soll "Yes" ausgeben, wenn der Graph einen Zyklus aufweist, andernfalls "No".
Beispiele
Eingabe | Ausgabe |
4 3
1 2
2 3
3 1
| Yes |
4 3
1 2
1 3
2 4 | No |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB