Wat is het breedtezoekalgoritme?

De breedte-eerst zoekalgoritme (BFS - Breadth-First Search) is een doorloop- of zoekalgoritme in een boom of graaf. Het begint bij de wortelknop (of een willekeurige knop als de graaf geen boom is) en onderzoekt al zijn directe buren, daarna de buren van deze buren, enzovoort, niveau voor niveau. BFS wordt geïmplementeerd met behulp van een wachtrij.

Werking:

1. Plaats de startknop in de wachtrij.
2. Terwijl de wachtrij niet leeg is:
   • Verwijder een knop uit de wachtrij.
   • Als de knop de gezochte is, stop de zoektocht.
   • Anders, plaats alle niet-bezochte buren van de knop in de wachtrij en markeer ze als bezocht.

Kenmerken:

• Volledigheid: Garandeert het vinden van een oplossing indien deze bestaat.
• Optimaliteit: Vindt de kortste weg in een gewichtloze graaf (waar de gewichten van de randen gelijk zijn).
• Tijdcomplexiteit: Afhankelijk van de structuur van de graaf, voor E randen en V knopen — O(V + E).
• Geheugencomplexiteit: O(V) in het slechtste geval, omdat bezochte knopen en de wachtrij moeten worden opgeslagen.

Toepassingen in QA:

• Het zoeken naar de kortste weg tussen knopen in testsituaties.
• Onderzoek naar alle bereikbare toestanden van het systeem tijdens testen van eindige automaten.
• Testen van de toegankelijkheid van alle pagina's van een website tijdens crawling.

Voorbeeld (boom doorlopen):

from collections import deque

# Voorbeeld van boomrepresentatie als een adjacency-lijst
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)

# Voorbeeld aanroep
# bfs(graph, 'A')
# Uitvoer:
# A
# B
# C
# D
# E
# F