Was ist der Breitensuchalgorithmus?

Der Breitensuchalgorithmus (BFS - Breadth-First Search) ist ein Traversierungs- oder Suchalgorithmus in einem Baum oder Graphen. Er beginnt mit dem Wurzelknoten (oder einem beliebigen Knoten, wenn der Graph kein Baum ist) und erkundet alle seine unmittelbaren Nachbarn, dann die Nachbarn dieser Nachbarn und so weiter, Ebene für Ebene. BFS wird unter Verwendung einer Warteschlange implementiert.

Funktionsprinzip:

1. Den Startknoten in die Warteschlange legen.
2. Solange die Warteschlange nicht leer ist:
   • Einen Knoten aus der Warteschlange entfernen.
   • Wenn der Knoten der gesuchte ist, die Suche beenden.
   • Andernfalls alle nicht besuchten Nachbarn des Knotens in die Warteschlange legen und sie als besucht markieren.

Eigenschaften:

• Vollständigkeit: Garantiert die Findung einer Lösung, falls sie existiert.
• Optimalität: Findet den kürzesten Weg in einem ungewichteten Graphen (bei gleichen Kantengewichten).
• Zeitkomplexität: Hängt von der Struktur des Graphen ab, für E Kanten und V Knoten — O(V + E).
• Speicherkomplexität: O(V) im schlimmsten Fall, da besuchte Knoten und die Warteschlange gespeichert werden müssen.

Anwendungen in QA:

• Suche nach dem kürzesten Weg zwischen Knoten in Testszenarien.
• Untersuchung aller erreichbaren Zustände des Systems bei Tests endlicher Automaten.
• Überprüfung der Erreichbarkeit aller Seiten einer Webseite beim Crawling.

Beispiel (Baumdurchlauf):

from collections import deque

# Beispiel für die Darstellung eines Baumes als Adjazenzliste
graph = {
    'A': ['B', 'C'],
    'B': ['D', 'E'],
    'C': ['F'],
    'D': [],
    'E': ['F'],
    'F': []
}

def bfs(graph, start_node):
    visited = set()
    queue = deque([start_node])
    visited.add(start_node)

    while queue:
        node = queue.popleft()
        print(node)

        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

# Beispielaufruf
# bfs(graph, 'A')
# Ausgabe:
# A
# B
# C
# D
# E
# F