Breitensuche (BFS) in Python
In dieser Lektion durchläufst du einen Graphen Ebene für Ebene mit der Breitensuche und einer deque als Warteschlange.
Einführung
Das Problem
Wie viele Schritte braucht es von einer Person zu einer anderen in einem sozialen Netzwerk, oder von einem Feld eines Labyrinths zum Ausgang? Die Breitensuche erkundet in Ringen nach Entfernung. Wenn sie einen Knoten zum ersten Mal erreicht, dann also über einen kürzesten Weg.
Stell es dir so vor
Breitensuche ist wie Wellen auf einem Teich. Wirf am Start einen Stein, und die Welle erreicht zuerst alles einen Schritt entfernt, dann alles zwei Schritte entfernt und so weiter. Nichts Entfernteres wird berührt, bevor alles Nähere erreicht ist.
queue = deque(["A"])🪨 Den Stein bei A werfennode = queue.popleft()🌊 Den nächsten Knoten nach Entfernung nehmenif neighbor not in visited:🔎 Noch nicht erreicht?queue.append(neighbor)➕ Zum nächsten Ring hinzufügenDie Breitensuche (BFS) besucht einen Graphen Ebene für Ebene von einem Startknoten aus und nutzt dafür eine Queue. So findet sie kürzeste Wege in Graphen ohne Gewichte.
Das Wichtigste
queueenthält die Knoten, die auf ihre Erkundung warten, die ältesten zuerst.visitedvermerkt schon gefundene Knoten, sodass keiner doppelt hinzukommt und Zyklen nicht endlos laufen.node = queue.popleft()nimmt den nächsten Knoten; seine unbesuchten Nachbarn stellen sich hinten an.orderzeigt A, dann seine Nachbarn B und C, dann D und E eine Ebene weiter.
Wann verwendet man das?
- Kürzeste Wege in ungewichteten Graphen, Gittern und Labyrinthen.
- Grade der Bekanntschaft in sozialen Netzwerken.
- Webcrawler und alles finden, was von einem Startpunkt aus erreichbar ist.
Wann du es nicht brauchst
- Kanten haben unterschiedliche Kosten, etwa Straßenentfernungen: Nimm den Dijkstra-Algorithmus.
- Du musst einen Weg ganz erkunden, bevor du andere versuchst, etwa beim Backtracking: Nimm die Tiefensuche.
Breitensuche (BFS) in Python visualisieren
O(V + E)Mit Start oder Schritt kannst du jeden Vergleich und jede Datenbewegung verfolgen.
Beispielcode
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)
Ergebnis der Ausführung
['A', 'B', 'C', 'D', 'E']
Erklärung des Codes
Die Warteschlange queue enthält die Knoten, die noch besucht werden müssen, und gibt sie in der Reihenfolge heraus, in der sie hinzugefügt wurden. Die Menge visited merkt sich bereits gefundene Knoten, damit ein Knoten nicht mehrfach besucht wird, wenn der Graph Zyklen hat. Die Besuchsreihenfolge ist A, B, C, D, E, die Komplexität ist O(V + E), wobei V die Zahl der Knoten und E die Zahl der Kanten ist.
Ä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
Knoten zu spät als besucht markieren
Wird ein Knoten erst beim Herausnehmen aus der Queue markiert, kann er viele Male hinzugefügt werden.
node = queue.popleft()
visited.add(node)
for neighbor in graph[node]:
if neighbor not in visited:
queue.append(neighbor)
for neighbor in graph[node]:
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)
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.
- Can We Split Into Two Teams? Decide whether people can be assigned to two teams so that each listed pair is on opposite teams. Mittel
- Tree Diameter A tree is a connected undirected graph with no cycles. Mittel
- Count Islands Count groups of connected land cells in a grid. Mittel