Breitensuche-Algorithmus (BFS)

8.1 Funktionsweise des BFS-Algorithmus

Breitensuche (Breadth-First Search, BFS) — ist ein Algorithmus zum Durchlaufen oder Suchen in einem Graphen, der bei einem Startknoten beginnt und alle benachbarten Knoten auf der aktuellen Ebene untersucht, bevor er zu den Knoten der nächsten Ebene übergeht.

Schritte des Algorithmus:

1. Wir beginnen mit dem ausgewählten Startknoten und legen ihn in die Warteschlange.
2. Solange die Warteschlange nicht leer ist, führen wir die folgenden Aktionen aus:
   • Wir entfernen den Knoten von der Spitze der Warteschlange und markieren ihn als besucht.
   • Für jeden unbesuchten benachbarten Knoten fügen wir ihn in die Warteschlange ein.
3. Wir wiederholen Schritt 2, bis alle Knoten besucht sind, die vom Startknoten aus erreichbar sind.

Visualisierung:

Zeitkomplexität:

O(V + E), wobei V die Anzahl der Knoten und E die Anzahl der Kanten ist.

Jeder Knoten und jede Kante des Graphen wird einmal besucht.

Raumkomplexität:

O(V), da eine Warteschlange zur Speicherung der Knoten verwendet wird sowie Arrays zum Speichern des Zustands (besuchte Knoten).

8.2 Implementierung von BFS mit einer Warteschlange

Die Breitensuche lässt sich gut mit einer Datenstruktur wie der Warteschlange umsetzen.

Implementierung von BFS mit einer Warteschlange:

from collections import deque

def bfs(graph, start):
    visited = set()
    queue = deque([start])
            
    while queue:
        vertex = queue.popleft()
        if vertex not in visited:
            visited.add(vertex)
            print(vertex)  # Verarbeitung des Knotens
            
            for neighbor in graph[vertex]:
                if neighbor not in visited:
                    queue.append(neighbor)
            
# Beispiel der Nutzung:
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B'],
    'F': ['C']
}
bfs(graph, 'A')

8.3 Bidirektionale Breitensuche

BFS wird oft in Spielen verwendet, wenn der kürzeste Weg zwischen zwei Punkten in einer komplexen Landschaft gefunden werden muss. Diese Aufgabe lässt sich leicht auf die Suche nach einem Weg in einem Graphen zwischen zwei Knoten reduzieren. Die Kanten eines solchen Graphen sind alle passierbaren Wege auf der Karte.

Um den Weg schneller zu finden, wird er meist von beiden Enden gesucht. Hierfür wird die bidirektionale Breitensuche angewendet.

Funktionsprinzip

Die bidirektionale Breitensuche (Bidirectional BFS) ist eine optimierte Version des BFS-Algorithmus, die zwei parallele Durchläufe des Graphen ausführt: einen vom Startknoten und einen vom Zielknoten. Die Durchläufe werden fortgesetzt, bis sich die beiden Durchläufe treffen, was die Anzahl der überprüften Knoten und Kanten im Vergleich zum klassischen BFS erheblich reduziert.

Schritte des Algorithmus:

• Initialisierung von zwei Warteschlangen: eine für den Durchlauf vom Startknoten, die andere — vom Zielknoten.
• Initialisierung von zwei Mengen besuchter Knoten zur Verfolgung besuchter Knoten in beiden Richtungen.
• Abwechselnde Durchführung des Graphendurchlaufs aus zwei Warteschlangen.
• Bei jedem Schritt wird überprüft, ob sich die Mengen besuchter Knoten überschneiden. Wenn eine Überschneidung gefunden wird, existiert ein Weg.
• Der Prozess wird fortgesetzt, bis ein überschneidender Knoten gefunden wird oder die Warteschlangen leer sind.

Zeitkomplexität

Im besten Fall: O(2 * (V + E)) = O(V + E), wobei V die Anzahl der Knoten und E die Anzahl der Kanten ist.

Die bidirektionale BFS durchläuft in der Regel weniger Knoten als das einseitige BFS, insbesondere in großen Graphen.

Raumkomplexität:

O(V) für die Speicherung von zwei Warteschlangen und zwei Mengen besuchter Knoten.

Beispiel für die Implementierung der bidirektionalen BFS

Das Beispiel ist sehr lang — der Algorithmus ist dreimal so lang wie die unidirektionale Suche — deshalb werde ich ihn nicht hier anführen. Wenn er wirklich benötigt wird, wirst du in der Lage sein, ihn selbst zu schreiben.

8.4 Beispielaufgaben, die mit BFS gelöst werden

Klassische Beispielaufgaben, die mit BFS gelöst werden:

1. Suche nach dem kürzesten Weg in einem ungerichteten Graphen:

BFS wird verwendet, um den kürzesten Weg (minimale Anzahl von Kanten) vom Startknoten zum Zielknoten in einem ungerichteten Graphen zu finden.

Anwendung:

• In Navigationssystemen zur Suche nach dem kürzesten Weg zwischen Punkten.
• In der Netzwerkanalyse zur Suche nach dem kürzesten Datenübertragungsweg.

2. Überprüfung der Zusammenhang eines Graphen:

Überprüfung, ob der Graph zusammenhängend ist, d. h. ob ein Weg zwischen beliebigen zwei Knoten existiert.

Anwendung:

• In der Netzwerkanalyse zur Überprüfung der Netzwerkzusammenhang.
• In der Analyse sozialer Netzwerke zur Überprüfung der Zusammenhang einer Nutzergruppe.

3. Generierung von Labyrinthen:

Verwendung von BFS zur Generierung zufälliger Labyrinthe mit gegebenen Eigenschaften.

Anwendung:

• In Spieleanwendungen zur Erstellung von Labyrinthen.
• In der Robotik zur Testung von Navigationsalgorithmen.

4. Breitensuche in Bäumen:

BFS wird verwendet, um Bäume zu durchlaufen, um Aktionen auf jeder Ebene des Baumes auszuführen (z. B. Drucken aller Knoten auf jeder Ebene).

Anwendung:

• In Datenvisualisierungsaufgaben, bei denen Daten nach Ebenen angezeigt werden müssen.
• In Planungsaufgaben, bei denen Aktionen auf jeder Ebene der Hierarchie ausgeführt werden müssen.

5. Überprüfung der Zweifarbigkeit eines Graphen:

Überprüfung, ob der Graph zweifarbig ist, d. h. ob die Knoten in zwei Mengen aufgeteilt werden können, so dass Kanten nur zwischen Knoten aus verschiedenen Mengen existieren.

Anwendung:

• In der Graphentheorie zur Überprüfung der Zweifarbigkeit eines Graphen.
• In Aufgaben zur Graphenfärbung, bei denen überprüft werden muss, ob der Graph mit zwei Farben gefärbt werden kann.