Breadth-First Search (BFS)

L'algoritmo Breadth-First Search esplora un grafo o un albero visitando i nodi livello per livello. È impiegato di frequente nelle coding interview per trovare il percorso più breve in strutture senza pesi o per verificare la connettività dei nodi.

🚀 Quando usarlo

Utilizza BFS quando:

• Devi trovare il percorso più breve in un grafo non pesato
• Vuoi controllare la raggiungibilità di un nodo
• Hai bisogno di analizzare un albero per livelli
• Cerchi la soluzione minima in uno spazio di stati

📺 Varianti principali del BFS

Variante	Descrizione
Iterativo con coda	Implementazione standard che sfrutta una struttura FIFO
Bidirezionale	Partenza contemporanea da sorgente e destinazione per ridurre lo spazio di ricerca
Layered BFS	Utile per costruire livelli o per problemi di flusso

✏️ Esempio classico: Percorso più breve in un labirinto

from collections import deque

def shortest_path(grid, start, end):
    rows, cols = len(grid), len(grid[0])
    queue = deque([(*start, 0)])
    visited = set([start])

    while queue:
        r, c, dist = queue.popleft()
        if (r, c) == end:
            return dist
        for dr, dc in [(1,0), (-1,0), (0,1), (0,-1)]:
            nr, nc = r + dr, c + dc
            if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] != '#' and (nr, nc) not in visited:
                visited.add((nr, nc))
                queue.append((nr, nc, dist + 1))
    return -1

✅ Complessità:

• Tempo: O(V + E)
• Spazio: O(V)

🫤 Problemi comuni

Nome	Difficoltà	Pattern	Link
Binary Tree Level Order Traversal	Easy	BFS di albero	Leetcode #102
Shortest Path in Binary Matrix	Medium	BFS su griglia	Leetcode #1091
Word Ladder	Hard	BFS su grafo	Leetcode #127

💡 Consigli utili

• Usa sempre una coda per gestire l'ordine di visita.
• Tieni traccia dei nodi già visitati per evitare cicli.
• Valuta BFS bidirezionale quando il grafo è molto grande.

📚 Continua con

👉 Depth-First Search →