Python-Algorithmen

Breitensuche (BFS) in Python

In dieser Lektion durchläufst du einen Graphen Ebene für Ebene mit der Breitensuche und einer deque als Warteschlange.

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

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.

Von Wellen im Teich zum Code
queue = deque(["A"])🪨 Den Stein bei A werfen
node = queue.popleft()🌊 Den nächsten Knoten nach Entfernung nehmen
if neighbor not in visited:🔎 Noch nicht erreicht?
queue.append(neighbor)➕ Zum nächsten Ring hinzufügen
Nächste Knoten zuerst, mit einer Queue.
In einem Satz

Die 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

  1. queue enthält die Knoten, die auf ihre Erkundung warten, die ältesten zuerst.
  2. visited vermerkt schon gefundene Knoten, sodass keiner doppelt hinzukommt und Zyklen nicht endlos laufen.
  3. node = queue.popleft() nimmt den nächsten Knoten; seine unbesuchten Nachbarn stellen sich hinten an.
  4. order zeigt 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

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

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.

  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

Knoten zu spät als besucht markieren

Wird ein Knoten erst beim Herausnehmen aus der Queue markiert, kann er viele Male hinzugefügt werden.

Problem
node = queue.popleft()
visited.add(node)
for neighbor in graph[node]:
    if neighbor not in visited:
        queue.append(neighbor)
Lösung
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.

Alle Challenges