Tiefensuche (DFS) in Python
In dieser Lektion durchläufst du einen Graphen mit der Tiefensuche, umgesetzt als rekursive Funktion.
Einführung
Das Problem
Einen Weg aus einem Labyrinth finden, prüfen, ob ein Graph einen Zyklus hat, oder voneinander abhängige Aufgaben ordnen: Dafür musst du einem Weg so weit folgen, wie er geht, bevor du einen anderen versuchst. Das ist die Tiefensuche.
Stell es dir so vor
Tiefensuche ist, wie du eine Höhle mit einem Wollknäuel erkundest. Du folgst einem Tunnel so tief, wie er geht. An einer Sackgasse folgst du dem Faden zurück zur letzten Abzweigung und versuchst den nächsten Tunnel. Erkundete Tunnel markierst du, damit du keinen zweimal gehst.
visited.add(node)🧵 Diesen Tunnel als erkundet markierenfor neighbor in graph[node]:🔀 Jeden Tunnel von hier aus ansehendepth_first(neighbor, visited)⬇️ In den ersten unerkundeten tiefer hineingehenreturn order↩️ Sackgasse: dem Faden zurück folgenDie Tiefensuche (DFS) erkundet einen Graphen, indem sie einem Zweig so tief wie möglich folgt, bevor sie zurückgeht. Meist nutzt sie dafür Rekursion oder einen Stack.
Das Wichtigste
visited.add(node)markiert den Knoten, damit Zyklen keine endlose Rekursion auslösen.for neighbor in graph[node]:schaut sich jeden Nachbarn der Reihe nach an.order.extend(depth_first(neighbor, visited))erkundet den ganzen Zweig unter einem Nachbarn, bevor der nächste drankommt.- Das Ergebnis besucht D vor C, weil der Zweig von B zuerst fertig wird.
Wann verwendet man das?
- Irgendeinen Weg finden, Labyrinthe und Rätsel mit Backtracking lösen.
- Zyklen erkennen und Aufgaben mit Abhängigkeiten ordnen (topologische Sortierung).
- Alle zusammenhängenden Teile eines Graphen erkunden.
Wann du es nicht brauchst
- Du brauchst den kürzesten Weg: Die Tiefensuche findet vielleicht zuerst einen langen Weg; nimm die Breitensuche.
- Sehr tiefe Graphen: Rekursion kann an Pythons Grenze stoßen; nimm einen expliziten Stack.
Tiefensuche (DFS) in Python visualisieren
O(V + E)Mit Start oder Schritt kannst du jeden Vergleich und jede Datenbewegung verfolgen.
Beispielcode
graph = {"A": ["B", "C"], "B": ["D"], "C": ["E"], "D": [], "E": []}
def depth_first(node, visited=None):
visited = visited or set()
visited.add(node)
order = [node]
for neighbor in graph[node]:
if neighbor not in visited:
order.extend(depth_first(neighbor, visited))
return order
print(depth_first("A"))
Ergebnis der Ausführung
['A', 'B', 'D', 'C', 'E']
Erklärung des Codes
Die Menge visited merkt sich besuchte Knoten, damit nichts doppelt verarbeitet wird und bei Zyklen keine Endlosschleife entsteht. Jeder rekursive Aufruf geht tiefer in einen noch nicht besuchten Nachbarn, deshalb besucht das Programm A, B, D und kehrt erst dann zurück, um C und E zu besuchen. Der Aufrufstapel übernimmt die Rolle des Stapels im Algorithmus, die Komplexität ist O(V + E).
Ändere die Werte und führe das Programm im CodeUtility Python Online-Compiler aus, ohne Python lokal zu installieren.
Übungen zur Vertiefung
Ändere den Code anhand der folgenden Vorschläge. Wenn du selbst etwas änderst und das Ergebnis beobachtest, verstehst du viel mehr, als wenn du den Code nur liest.
- Teste mit einer leeren Liste, einer Liste mit nur einem Element und einer Liste mit doppelten Werten.
- Gib den Zustand nach jedem Schritt aus, um den Algorithmus bei der Arbeit zu beobachten.
- Miss die Laufzeit mit 100, 1.000 und 10.000 Elementen und vergleiche sie mit einer anderen Lösung.
Häufige Fehler
Ein veränderliches Standardargument verwenden
visited=set() würde zwischen getrennten Aufrufen geteilt.
def depth_first(node, visited=set()):
def depth_first(node, visited=None):
visited = visited or set()
Lektion fertig?
Markiere sie als gelernt, um deinen Fortschritt zu verfolgen.
Mit einer Challenge üben
Nutze den Inhalt dieser Lektion, um ein echtes Problem zu lösen. Jede Challenge läuft im Browser, mit sofortigen Tests und einem KI-Review.
- Count Islands Count groups of connected land cells in a grid. Mittel
- Strongly Connected Components Count groups of nodes that can all reach each other. Schwierig
- Longest Path in a DAG Find the heaviest path in a task dependency graph. Schwierig