Python-Algorithmen

Tiefensuche (DFS) in Python

In dieser Lektion durchläufst du einen Graphen mit der Tiefensuche, umgesetzt als rekursive Funktion.

  • Fortgeschritten
  • 2 Min. Lesezeit
  • 1 ausführbares Beispiel

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.

Von der Höhlenerkundung zum Code
visited.add(node)🧵 Diesen Tunnel als erkundet markieren
for neighbor in graph[node]:🔀 Jeden Tunnel von hier aus ansehen
depth_first(neighbor, visited)⬇️ In den ersten unerkundeten tiefer hineingehen
return order↩️ Sackgasse: dem Faden zurück folgen
Erst in die Tiefe gehen, dann zurück und den nächsten Zweig versuchen.
In einem Satz

Die 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

  1. visited.add(node) markiert den Knoten, damit Zyklen keine endlose Rekursion auslösen.
  2. for neighbor in graph[node]: schaut sich jeden Nachbarn der Reihe nach an.
  3. order.extend(depth_first(neighbor, visited)) erkundet den ganzen Zweig unter einem Nachbarn, bevor der nächste drankommt.
  4. 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

Code ausführen →
main.py
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"))
Run-Button für dieses Beispiel erstellen

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.

  1. Teste mit einer leeren Liste, einer Liste mit nur einem Element und einer Liste mit doppelten Werten.
  2. Gib den Zustand nach jedem Schritt aus, um den Algorithmus bei der Arbeit zu beobachten.
  3. Miss die Laufzeit mit 100, 1.000 und 10.000 Elementen und vergleiche sie mit einer anderen Lösung.
Im Python-Compiler ausführen →

Häufige Fehler

Ein veränderliches Standardargument verwenden

visited=set() würde zwischen getrennten Aufrufen geteilt.

Problem
def depth_first(node, visited=set()):
Lösung
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.

Alle Challenges