Kas yra pločio paieškos algoritmas?

Plačiausios paieškos algoritmas (BFS - Breadth-First Search) — tai apėjimo arba paieškos algoritmas medyje arba grafe. Jis pradeda nuo šaknies mazgo (arba atsitiktinio mazgo, jei grafas nėra medis) ir tiria visus jo tiesioginius kaimynus, tada tiria jų kaimynus ir taip toliau, lygmenimis. BFS įgyvendinamas naudojant eilę.

Veikimo principas:

1. Įdėti pradinį mazgą į eilę.
2. Kol eilė nėra tuščia:
   • Išimti mazgą iš eilės.
   • Jei mazgas yra ieškomas, sustabdyti paiešką.
   • Kitaip, įdėti į eilę visus jo neaplankytus kaimynus ir pažymėti juos kaip aplankytus.

Savybės:

• Visiškumas: Garantuoja sprendimo radimą, jei jis egzistuoja.
• Optimumas: Randa trumpiausią kelią ne svoriniu grafe (kurio briaunų svoriai lygūs).
• Laiko sudėtingumas: Priklauso nuo grafo struktūros, E briaunų ir V viršūnių atveju — O(V + E).
• Atminties sudėtingumas: O(V) blogiausiu atveju, nes reikia saugoti aplankytas viršūnes ir eilę.

Taikymas QA:

• Trumpiausio kelio tarp mazgų paieška testų scenarijuose.
• Visų pasiekiamų sistemos būsenų tyrimas baigiamųjų automatų testavime.
• Visų tinklalapio puslapių prieinamumo testavimas per naršymą.

Pavyzdys (medžio apėjimas):

from collections import deque

# Medžio vaizdavimas kaip sąrašo sąsajų žemėlapis
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)

# Pavyzdinis iškvietimas
# bfs(graph, 'A')
# Rezultatas:
# A
# B
# C
# D
# E
# F