DFS, Rekursion und iterative Stapel
Erkunden Sie tief und vermeiden Sie Rekursionslimits
DFS, Rekursion und iterative Stapel ist eine kostenlose Competitive Programming Academy-Lektion auf CoddyKit. Dies ist Lektion 3 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.
Was DFS macht
DFS geht einen Pfad so tief wie möglich entlang, kehrt dann zurück und versucht den nächsten. Stellen Sie sich vor, Sie erkunden einen Irrgarten Gang für Gang. 🧭
DFS vs. BFS
BFS breitet sich ringförmig aus, während DFS zuerst in die Tiefe geht. Beide besuchen jeden erreichbaren Knoten, jedoch in einer völlig anderen Reihenfolge.
Die rekursive Struktur
Eine rekursive DFS markiert einen Knoten als visited und ruft sich anschließend für jeden unbesuchten Nachbarn selbst auf. Der Aufrufstapel merkt sich, wohin zurückgekehrt werden muss.
def dfs(u):
visited[u] = True
for v in adj[u]:
if not visited[v]:
dfs(v)Vor der Rekursion markieren
Setzen Sie visited, sobald Sie einen Knoten betreten, und zwar vor dem Erkunden seiner Nachbarn. Andernfalls führen Zyklen zu einer unendlichen Rekursion.
Die Falle der Rekursionsgrenze
Python begrenzt die Rekursion auf etwa 1000 Aufrufe. Ein tiefer Graph löst einen RecursionError aus, der als Laufzeitfehler gewertet wird.
Die Grenze erhöhen
Eine schnelle Lösung besteht darin, die Grenze mit setrecursionlimit anzuheben. Setzen Sie sie vor dem Ausführen von DFS über die maximal zu erwartende Tiefe.
import sys
sys.setrecursionlimit(300000)Stattdessen iterativ vorgehen
Die sicherste Lösung ist eine iterative DFS mit einem eigenen Stapel. Ohne Aufrufstapel gibt es keinen Rekursionsabsturz.
stack = [start]Vom Stapel entnehmen
Entnehmen Sie in jedem Schritt das oberste Element des Stapels. Zuletzt hinein, zuerst heraus sorgt dafür, dass DFS zuerst dem zuletzt begonnenen Pfad in die Tiefe folgt.
u = stack.pop()Die Nachbarn auf den Stapel legen
Legen Sie nach dem Entnehmen von u jeden unbesuchten Nachbarn auf den Stapel. Markieren Sie sie, damit sie nicht erneut hinzugefügt werden.
for v in adj[u]:
if not visited[v]:
visited[v] = True
stack.append(v)Die vollständige iterative Schleife
Wiederholen Sie das Entnehmen und Hinzufügen, solange der Stapel Knoten enthält. Wenn er leer ist, wurde jeder erreichbare Knoten besucht.
while stack:
u = stack.pop()
for v in adj[u]:
if not visited[v]:
visited[v] = True
stack.append(v)Die gleiche Laufzeit wie BFS
Wie BFS besucht auch DFS jeden Knoten und jede Kante einmal und läuft daher in O(n + m). Entscheiden Sie anhand der für die Aufgabe passenden Reihenfolge.
Kurztest
Ihre rekursive DFS stürzt bei einem tiefen Graphen ab. Warum?
Rückblick
Sie führen DFS rekursiv oder mit einem eigenen Stapel aus, markieren Knoten beim Betreten und wechseln bei tiefen Graphen zur iterativen Variante. 🎉
Häufig gestellte Fragen
Ist die Lektion „DFS, Rekursion und iterative Stapel“ kostenlos?
Ja — der vollständige Text von „DFS, Rekursion und iterative Stapel“ 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 „DFS, Rekursion und iterative Stapel“?
Erkunden Sie tief und vermeiden Sie Rekursionslimits 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 3 von 4.
Wie lange dauert die Lektion „DFS, Rekursion und iterative Stapel“?
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
- Adjazenzlisten aus der Eingabe
- BFS für kürzeste ungewichtete Pfade
- DFS, Rekursion und iterative Stapel
- Zusammenhängende Komponenten und Flood Fill