Cos'è l'algoritmo di ricerca in ampiezza?

L'algoritmo di ricerca in ampiezza (BFS - Breadth-First Search) è un algoritmo di attraversamento o ricerca in un albero o grafo. Inizia dal nodo radice (o da un nodo arbitrario se il grafo non è un albero) e esplora tutti i suoi vicini immediati, poi esplora i vicini di questi vicini e così via, livello per livello. BFS viene implementato utilizzando una coda.

Principio di funzionamento:

1. Inserire il nodo iniziale nella coda.
2. Finché la coda non è vuota:
   • Estrare un nodo dalla coda.
   • Se il nodo è quello cercato, interrompere la ricerca.
   • Altrimenti, inserire nella coda tutti i suoi vicini non visitati e marcarli come visitati.

Caratteristiche:

• Completezza: Garantisce di trovare una soluzione se esiste.
• Ottimalità: Trova il percorso più breve in un grafo senza pesi (dove i pesi degli archi sono uguali).
• Complessità temporale: Dipende dalla struttura del grafo, per E archi e V vertici — O(V + E).
• Complessità di memoria: O(V) nel peggiore dei casi, poiché bisogna memorizzare i vertici visitati e la coda.

Applicazioni in QA:

• Ricerca del percorso più breve tra nodi in scenari di test.
• Esplorazione di tutti gli stati raggiungibili del sistema durante i test di automi finiti.
• Test di accessibilità di tutte le pagine di un sito web durante il crawling.

Esempio (attraversamento di un albero):

from collections import deque

# Esempio di rappresentazione di un albero come dizionario di adiacenza
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)

# Esempio di chiamata
# bfs(graph, 'A')
# Output:
# A
# B
# C
# D
# E
# F