Mi az a szélességi keresési algoritmus?

A szélességi keresés algoritmusa (BFS - Breadth-First Search) egy bejárási vagy keresési algoritmus egy fában vagy gráfban. A gyökércsomóponttól (vagy tetszőleges csomóponttól, ha a gráf nem fa) indulva, feltérképezi az összes közvetlen szomszédját, majd ezek szomszédait, és így tovább, szintenként. A BFS egy sor használatával valósul meg.

Működési elv:

1. Helyezze az induló csomópontot a sorba.
2. Amíg a sor nem üres:
   • Vegyen ki egy csomópontot a sorból.
   • Ha a csomópont a keresett, állítsa le a keresést.
   • Ellenkező esetben, helyezze a nem látogatott szomszédokat a sorba, és jelölje meg őket látogatottként.

Jellemzők:

• Teljesség: Garantálja a megoldás megtalálását, ha létezik.
• Optimális: Megtalálja a legrövidebb utat egy súlyozatlan gráfban (ahol az élek súlya egyenlő).
• Időbonyolultság: A gráf szerkezetétől függ, E él és V csúcs esetén — O(V + E).
• Memória: O(V) a legrosszabb esetben, mivel tárolni kell a látogatott csúcsokat és a sort.

Alkalmazások QA-ban:

• A legrövidebb út keresése csomópontok között tesztesetekben.
• Az összes elérhető állapot feltérképezése a rendszerben végzett végpont-automaták tesztelése során.
• Az összes oldal elérhetőségének tesztelése weboldalon crawling közben.

Példa (fa bejárása):

from collections import deque

# Példa egy fa reprezentációjára szomszédsági listaként
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élda hívás
# bfs(graph, 'A')
# Kimenet:
# A
# B
# C
# D
# E
# F