Co je to algoritmus hledání do šířky?

Algoritmus hledání do šířky (BFS - Breadth-First Search) je algoritmus průchodu nebo hledání v stromu nebo grafu. Začíná od kořenového uzlu (nebo libovolného uzlu, pokud graf není strom) a prozkoumá všechny jeho přímé sousedy, poté sousedy těchto sousedů a tak dále, úroveň po úrovni. BFS je implementován pomocí fronty.

Princip fungování:

Umístěte počáteční uzel do fronty.
Dokud není fronta prázdná:
- Odeberte uzel z fronty.
- Pokud je uzel hledaný, ukončete hledání.
- Jinak vložte všechny jeho nenavštívené sousedy do fronty a označte je jako navštívené.

Charakteristiky:

Kompletnost: Zaručuje nalezení řešení, pokud existuje.
Optimálnost: Najde nejkratší cestu v bezešvém grafu (kde váhy hran jsou stejné).
Časová složitost: Závisí na struktuře grafu, pro E hran a V vrcholů — O(V + E).
Paměťová složitost: O(V) v nejhorším případě, protože je třeba uložit navštívené vrcholy a frontu.

Použití v QA:

Vyhledávání nejkratší cesty mezi uzly v testovacích scénářích.
Zkoumání všech dosažitelných stavů systému při testování konečných automatů.
Testování dostupnosti všech stránek webu při crawlingu.

Příklad (průchod stromem):

from collections import deque

# Příklad reprezentace stromu jako seznam sousedství
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)

# Příklad volání
# bfs(graph, 'A')
# Výstup:
# A
# B
# C
# D
# E
# F