Tiefensuche (DFS) in Python
DFS verwendet Rekursion oder einen expliziten Stack, um Graphen und Bäume zu durchlaufen.
Was ist Tiefensuche (DFS)?
DFS verwendet Rekursion oder einen expliziten Stack, um Graphen und Bäume zu durchlaufen.
Verfolge einen Pfad möglichst tief, bevor du zurückgehst.
Wann wird dieser Ansatz verwendet?
- Algorithmen und Datenstrukturen anhand von ausführbarem Code verstehen.
- Die einzelnen Verarbeitungsschritte und Randfälle nachvollziehen.
- Laufzeit und Speicherbedarf verschiedener Lösungswege vergleichen.
Tiefensuche (DFS) in Python visualisieren
O(V+E)Mit Start oder Schritt kannst du jeden Vergleich und jede Datenbewegung verfolgen.
Beispielcode
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"))Erwartete Ausgabe
['A', 'B', 'D', 'C', 'E']So funktioniert es
Jeder Knoten und jede Kante wird höchstens einmal verarbeitet. Laufzeit O(V+E), Speicher O(V).
Ändere die Werte und führe das Programm im CodeUtility Python Online-Compiler aus, ohne Python lokal zu installieren.
Übungsaufgaben
Verändere Eingaben und Randfälle, bevor du die Lösung mit größeren Datenmengen testest.
- Teste leere Eingaben, ein Element und doppelte Werte.
- Gib den Zustand nach jedem Schritt aus.
- Vergleiche Laufzeit und Speicherbedarf mit einem alternativen Verfahren.