Breitensuche (BFS) in Python
BFS besucht zuerst alle direkten Nachbarn und verwendet dafür eine Queue.
Was ist Breitensuche (BFS)?
BFS besucht zuerst alle direkten Nachbarn und verwendet dafür eine Queue.
Durchsuche einen Graphen Ebene für Ebene.
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.
Breitensuche (BFS) in Python visualisieren
O(V+E)Mit Start oder Schritt kannst du jeden Vergleich und jede Datenbewegung verfolgen.
Beispielcode
main.py
from collections import deque
graph = {"A": ["B", "C"], "B": ["D"], "C": ["E"], "D": [], "E": []}
queue = deque(["A"])
visited = {"A"}
order = []
while queue:
node = queue.popleft()
order.append(node)
for neighbor in graph[node]:
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)
print(order)Erwartete Ausgabe
['A', 'B', 'C', 'D', 'E']So funktioniert es
Eine visited-Menge verhindert Mehrfachbesuche. Mit Adjazenzlisten beträgt die Laufzeit O(V+E) und der Speicherbedarf 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.