Czym jest algorytm przeszukiwania w szerz?

Algorytm przeszukiwania w szerz (BFS - Breadth-First Search) jest algorytmem przeszukiwania lub odwiedzania drzewa lub grafu. Zaczyna od węzła korzeniowego (lub dowolnego węzła, jeśli graf nie jest drzewem) i bada wszystkich jego bezpośrednich sąsiadów, następnie sąsiadów tych sąsiadów i tak dalej, poziom po poziomie. BFS jest realizowany przy użyciu kolejki.

Zasada działania:

1. Umieścić węzeł początkowy w kolejce.
2. Dopóki kolejka nie jest pusta:
   • Usunąć węzeł z kolejki.
   • Jeśli węzeł jest poszukiwany, zatrzymać wyszukiwanie.
   • W przeciwnym razie, umieścić w kolejce wszystkich nieodwiedzonych sąsiadów i oznaczyć ich jako odwiedzonych.

Charakterystyka:

• Kompletność: Gwarantuje znalezienie rozwiązania, jeśli ono istnieje.
• Optymalność: Znajduje najkrótszą ścieżkę w grafie bez wag (gdzie wagi krawędzi są równe).
• Złożoność czasowa: Zależy od struktury grafu, dla E krawędzi i V wierzchołków — O(V + E).
• Złożoność pamięciowa: O(V) w najgorszym przypadku, ponieważ trzeba przechowywać odwiedzone wierzchołki i kolejkę.

Zastosowania w QA:

• Szukanie najkrótszej ścieżki między węzłami w scenariuszach testowych.
• Badanie wszystkich osiągalnych stanów systemu podczas testowania automatów skończonych.
• Testowanie dostępności wszystkich stron internetowych podczas crawlingu.

Przykład (przeszukiwanie drzewa):

from collections import deque

# Przykład reprezentacji drzewa jako słownik sąsiedztwa
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)

# Przykład wywołania
# bfs(graph, 'A')
# Wynik:
# A
# B
# C
# D
# E
# F