Kas ir platuma meklēšanas algoritms?

Plaša meklēšanas algoritms (BFS - Breadth-First Search) — tas ir apmeklējuma vai meklēšanas algoritms kokā vai grafikā. Tas sākas no saknes mezgla (vai nejauša mezgla, ja grafiks nav koks) un pēta visus tā tiešos kaimiņus, tad kaimiņus šo kaimiņu un tā tālāk, līmenis pēc līmeņa. BFS tiek īstenots ar rindas izmantošanu.

Darba princips:

1. Ielikt sākuma mezglu rindā.
2. Kamēr rinda nav tukša:
   • Izņemt mezglu no rindas.
   • Ja mezgls ir meklētais, pārtraukt meklēšanu.
   • Pretējā gadījumā, ielikt visus tā neapmeklētus kaimiņus rindā un atzīmēt tos kā apmeklētus.

Īpašības:

• Pilnīgums: Garantē risinājuma atrašanu, ja tas pastāv.
• Optimālitāte: Atrod īsāko ceļu nevirsmas grafikā (kur malas ir vienādas).
• Laika sarežģītība: Atkarīga no grafika struktūras, E malu un V virsotņu gadījumā — O(V + E).
• Atmiņas sarežģītība: O(V) sliktākajā gadījumā, jo jāuzglabā apmeklētās virsotnes un rinda.

Pielietojums QA:

• Īsākā ceļa starp mezgliem meklēšana testu scenārijos.
• Visu sasniedzamo sistēmas stāvokļu pētīšana galīgo automātu testēšanā.
• Visu tīmekļa lapu pieejamības pārbaude ar rīkošanu.

Piemērs (koka apmeklējums):

from collections import deque

# Koka attēlojums kā blakus esošo saraksta grafiks
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)

# Piemērs izsaukšanai
# bfs(graph, 'A')
# Rezultāts:
# A
# B
# C
# D
# E
# F