Čo je to algoritmus vyhľadávania do šírky?

Algoritmus prehľadávania do šírky (BFS - Breadth-First Search) je algoritmus prechádzania alebo vyhľadávania v strome alebo grafe. Začína od koreňového uzla (alebo ľubovoľného uzla, ak graf nie je strom) a skúma všetkých jeho priame susedov, potom susedov týchto susedov a tak ďalej, úroveň po úrovni. BFS je implementovaný pomocou fronty.

Princíp fungovania:

1. Položte počiatočný uzol do fronty.
2. Kým fronta nie je prázdna:
   • Odstráňte uzol z fronty.
   • Ak je uzol hľadaný, ukončite vyhľadávanie.
   • Inak, vložte do fronty všetkých jeho nenavštívených susedov a označte ich ako navštívených.

Charakteristiky:

• Kompletnosť: Zaručuje nájdenie riešenia, ak existuje.
• Optimalita: Nájde najkratšiu cestu v grafe bez váh (kde váhy hrán sú rovnaké).
• Časová zložitosť: Závisí od štruktúry grafu, pre E hrán a V vrcholov — O(V + E).
• Pamäťová zložitosť: O(V) v najhoršom prípade, pretože je potrebné uložiť navštívené vrcholy a frontu.

Použitie v QA:

• Vyhľadávanie najkratšej cesty medzi uzlami v testovacích scenároch.
• Preskúmanie všetkých dostupných stavov systému počas testovania konečných automatov.
• Testovanie dostupnosti všetkých stránok webovej stránky počas crawlingu.

Príklad (prechádzanie stromu):

from collections import deque

# Príklad reprezentácie stromu ako zoznam susedstva
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)

# Príklad volania
# bfs(graph, 'A')
# Výstup:
# A
# B
# C
# D
# E
# F