Algoritmi di ricerca in ampiezza (BFS)

8.1 Principi di funzionamento dell'algoritmo BFS

Ricerca in ampiezza (Breadth-First Search, BFS) è un algoritmo di attraversamento o ricerca in un grafo che inizia dal vertice iniziale ed esplora tutti i suoi vertici adiacenti al livello corrente prima di passare ai vertici del livello successivo.

Passi dell'algoritmo:

1. Iniziamo con il vertice iniziale scelto e lo inseriamo in una coda.
2. Finché la coda non è vuota, eseguiamo i seguenti passaggi:
   • Estraiamo il vertice dalla testa della coda e lo segnamo come visitato.
   • Per ogni vertice adiacente non visitato lo aggiungiamo alla coda.
3. Ripetiamo il passo 2 finché non vengono visitati tutti i vertici raggiungibili dal vertice iniziale.

Visualizzazione:

Complessità temporale:

O(V + E), dove V è il numero di vertici, E è il numero di archi.

Ogni nodo e ogni arco del grafo vengono visitati una sola volta.

Complessità spaziale:

O(V), poiché si utilizza una coda per memorizzare i vertici e anche array per memorizzare lo stato (vertici visitati).

8.2 Implementazione del BFS utilizzando una coda

La ricerca in ampiezza è ben implementata utilizzando una struttura dati come la coda.

Implementazione del BFS utilizzando una coda:

from collections import deque

def bfs(graph, start):
    visited = set()
    queue = deque([start])
            
    while queue:
        vertex = queue.popleft()
        if vertex not in visited:
            visited.add(vertex)
            print(vertex)  # Elaborazione del nodo
            
            for neighbor in graph[vertex]:
                if neighbor not in visited:
                    queue.append(neighbor)
            
# Esempio di utilizzo:
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B'],
    'F': ['C']
}
bfs(graph, 'A')

8.3 Ricerca bidirezionale in ampiezza

BFS viene spesso utilizzato nei giochi quando è necessario trovare il percorso più breve tra due punti in un paesaggio complesso. Questo tipo di problema viene facilmente trasformato in un problema di ricerca del percorso in un grafo tra due vertici. Gli archi di tale grafo sono tutti i percorsi transitabili sulla mappa.

Ma per trovare il percorso più velocemente, di solito si cerca da entrambi i lati. Per questo si applica il BFS bidirezionale.

Principio di funzionamento

La ricerca bidirezionale in ampiezza (Bidirectional BFS) è una versione ottimizzata dell'algoritmo BFS, che esegue due attraversamenti paralleli del grafo: uno dal vertice iniziale e l'altro dal vertice di destinazione. Gli attraversamenti continuano finché i due attraversamenti non si incontrano, il che riduce significativamente il numero di vertici e archi verificati rispetto al BFS classico.

Passi dell'algoritmo:

• Inizializzazione di due code: una per l'attraversamento dal vertice iniziale, l'altra dal vertice di destinazione.
• Inizializzazione di due insiemi di vertici visitati per tracciare i vertici visitati in entrambe le direzioni.
• Esecuzione dell'attraversamento alternato del grafo dalle due code.
• A ogni passo si verifica se gli insiemi di vertici visitati si sovrappongono. Se si trova un'intersezione, il percorso esiste.
• Il processo continua finché non viene trovato un nodo di intersezione o le code non si svuotano.

Complessità temporale

Nel caso migliore: O(2 * (V + E)) = O(V + E), dove V è il numero di vertici, E è il numero di archi.

Il BFS bidirezionale di solito esegue l'attraversamento di un numero minore di vertici rispetto al BFS a singolo passaggio, specialmente nei grandi grafi.

Complessità spaziale:

O(V) per la memorizzazione delle due code e dei due insiemi di vertici visitati.

Esempio di implementazione del BFS bidirezionale

L'esempio è molto lungo - l'algoritmo è circa tre volte più lungo della ricerca unidirezionale - quindi non lo fornirò qui. Quando ne avrai veramente bisogno, sarai in grado di scriverlo da solo.

8.4 Esempi di problemi risolti con BFS

Esempi classici di problemi risolti con BFS:

1. Ricerca del percorso più breve in un grafo non orientato:

BFS è usato per trovare il percorso più breve (minimo numero di archi) dal vertice iniziale a quello di destinazione in un grafo non orientato.

Applicazione:

• Nei sistemi di navigazione per trovare il percorso più breve tra due punti.
• Nell'analisi delle reti per trovare il percorso più breve di trasmissione dati.

2. Verifica della connettività del grafo:

Verifica se il grafo è connesso, cioè se esiste un percorso tra qualsiasi coppia di vertici.

Applicazione:

• Nell'analisi delle reti per verificare la connettività della rete.
• Nell'analisi dei social network per verificare la connettività di un gruppo di utenti.

3. Generazione di labirinti:

Uso del BFS per generare labirinti casuali con proprietà date.

Applicazione:

• Nei giochi per creare labirinti.
• Nella robotica per testare algoritmi di navigazione.

4. Ricerca in ampiezza negli alberi:

BFS è usato per attraversare alberi, per eseguire operazioni su ogni livello dell'albero (ad esempio, stampare tutti i nodi a ogni livello).

Applicazione:

• Nei problemi di visualizzazione dei dati, dove è necessario visualizzare i dati per livelli.
• Nei problemi di pianificazione, dove è necessario eseguire operazioni su ogni livello della gerarchia.

5. Verifica della bipartizione del grafo:

Verifica se un grafo è bipartito, cioè se i suoi vertici possono essere divisi in due insiemi tali che gli archi esistono solo tra vertici di insiemi diversi.

Applicazione:

• Nella teoria dei grafi per verificare la bipartizione del grafo.
• Nei problemi di colorazione dei grafi, dove è necessario verificare se è possibile colorare il grafo con due colori.