Breadth-first search

Breadth-first search

Ordine di esplorazione dei nodi
Classe	Algoritmo di ricerca
Struttura dati	Grafo
Caso peggiore temporalmente	O( | V | + | E | ) = O(bd)
Caso peggiore spazialmente	O( | V | + | E | ) = O(bd)
Ottimale	Si (per grafi non ordinati)
Completo	Si

Nella teoria dei grafi, breadth-first search (BFS), ossia ricerca in ampiezza, è un algoritmo di visita per i grafi partendo da un vertice (o nodo) detto sorgente ed esplorando tutti i nodi del grafo stesso raggiungibili o non raggiungibili (in tal caso si parlerà di BFS totale).

Diversamente dalla visita in profondità per i grafi e dalle sue varianti (pre-ordine, ordine, post-ordine) sugli alberi, la visita in ampiezza è difficilmente implementabile come algoritmo puramente ricorsivo, ma è piuttosto un esempio di programmazione dinamica.

Descrizione

L'algoritmo si avvale di una coda in cui memorizza mano a mano i nodi visitati, che vengono inoltre marcati.

L'idea base è di partire con un solo vertice qualsiasi nella coda (in un albero, sarà la radice) ed eseguire ripetutamente l'operazione di "visitare" il vertice in cima alla coda, marcarlo ed aggiungere in fondo alla coda tutti i suoi vertici adiacenti non ancora marcati.

Se invece che una coda utilizziamo una pila (ovvero invece di aggiungere gli elementi nuovi in fondo li aggiungiamo in cima), otteniamo esattamente una visita in profondità (e più precisamente, nell'implementazione descritta, una in pre-ordine).

Nel caso in cui il grafo sia un albero, esiste un solo percorso per arrivare ad ogni vertice, per cui non è necessario marcare i vertici visitati.

BFS è un metodo di ricerca non informato, ed ha il suo obiettivo quello di espandere il raggio d'azione al fine di esaminare tutti i nodi del grafo sistematicamente, fino alla soluzione. In altre parole, la ricerca avviene in maniera esaustiva fino a quando non si sono visitati tutti i nodi del grafo. Questo algoritmo non è di tipo euristico.

Algoritmo

Dal punto di vista dell'algoritmo, tutti i nodi adiacenti ad un nodo, sono aggiunti ad una coda di tipo FIFO. In una tipica implementazione, i nodi che ancora non sono stati esaminati, sono posti in un contenitore (come una coda oppure una lista) etichettati come "non visitato", ed una volta esaminati, saranno collocati in un'altra struttura dati ed etichettati come "visitato".

• 1. All'inizio dell' algoritmo tutti i vertici sono bianchi tranne la sorgente da cui parte l'esecuzione dell'algoritmo.
• 2. Con l'andare avanti nella visita i vertici del grafo vengono colorati di grigio, ed inseriti nella coda, che in ogni istante conterrà tutti i nodi colorati di grigio, ma dei quali ancora non sono stati visitati gli adiacenti.
• 3. Quando tutti i nodi adiacenti ad un nodo grigio sono stati visitati e quindi colorati di grigio, il nodo verrà colorato di nero e rimosso da Q

Complessità

Il tempo di esecuzione totale di questo algoritmo è O(V+E) dove V è l'insieme dei vertici del grafo ed E è l'insieme degli archi che collegano i vertici.

Applicazione

Tipicamente i crawler, che navigano la rete per indicizzare le pagine, visitano l'enorme grafo che essa rappresenta (dove ogni pagina viene vista come un vertice ed ogni link come un arco) con una visita in ampiezza, dato che essa comporta alcuni vantaggi:

• quando un sito (le cui pagine si suppone siano strettamente interconnesse) viene visitato, viene probabilmente visitato nella sua interezza prima di allontanarsene
• se si incontra una pagina già visitata, è abbastanza probabile che essa sia stata visitata di recente (e che quindi sia memorizzata in qualche sistema di cache)

Fa eccezione il caso di un crawler il cui scopo non sia navigare tutte le pagine del web, ma cercare pagine che si trovano solo in determinati siti, oppure che abbia dei criteri per preferire alcuni link ad altri; allora si preferirà una visita in profondità.

Implementazione in Python

Per grafi

# R è il vertice da cui partiamo
coda = [R]
 
while coda:
    # operazione di dequeue
    vertice = coda.pop(0)
    vertice.visitato = True
    for adiacente in vertice.adiacenti:
        if not adiacente.visitato:
            # operazione di enqueue
            coda.append(adiacente)

Per alberi

# R è la radice
coda = [R]
 
while coda:
    # operazione di dequeue
    vertice = coda.pop(0)
    # operazione di enqueue su ogni figlio
    coda.extend(vertice.figli)

Voci correlate

• Grafo
• DFS - Ricerca in profondità
• Coda

Altri progetti

• Commons

• Wikimedia Commons contiene file multimediali su Breadth-first search

Portale Informatica

Portale Matematica