Ce este algoritmul de căutare în lățime?

Algoritmul de căutare în lățime (BFS - Breadth-First Search) este un algoritm de traversare sau căutare într-un arbore sau graf. Începe de la nodul rădăcină (sau un nod arbitrar dacă graful nu este un arbore) și explorează toți vecinii săi imediați, apoi vecinii acestor vecini și tot așa, nivel cu nivel. BFS se implementează folosind o coadă.

Principiul de funcționare:

1. Pune nodul inițial în coadă.
2. Atâta timp cât coada nu este goală:
   • Extrage un nod din coadă.
   • Dacă nodul este cel căutat, oprește căutarea.
   • Altfel, pune în coadă toți vecinii săi nevizitați și marchează-i ca fiind vizitați.

Caracteristici:

• Completitudine: Asigură găsirea unei soluții dacă aceasta există.
• Optimizare: Găsește cel mai scurt drum într-un graf fără greutate (unde greutățile muchiilor sunt egale).
• Complexitatea în timp: Depinde de structura grafului, pentru E muchii și V vârfuri — O(V + E).
• Complexitatea în memorie: O(V) în cel mai rău caz, deoarece trebuie să stochezi vârfurile vizitate și coada.

Aplicații în QA:

• Căutarea celui mai scurt drum între noduri în scenarii de testare.
• Explorarea tuturor stărilor accesibile ale sistemului în timpul testării automate.
• Testarea accesibilității tuturor paginilor unui site web în timpul crawling-ului.

Exemplu (parcurgerea unui arbore):

from collections import deque

# Exemplu de reprezentare a unui arbore ca listă de adiacență
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)

# Exemplu de apel
# bfs(graph, 'A')
# Output:
# A
# B
# C
# D
# E
# F