Ricerca in ampiezza

Nella teoria dei grafi, la ricerca in ampiezza (in inglese breadth-first search, in acronimo BFS) è un algoritmo di ricerca per grafi che partendo da un vertice (o nodo) detto sorgente permette di cercare il cammino fino ad un altro nodo scelto e connesso al nodo sorgente.

Ricerca in ampiezza
Ordine di esplorazione dei nodi
Classe	Algoritmo di ricerca
Struttura dati	Grafo
Caso peggiore temporalmente	$O(|V|+|E|)=O(b^{d})$
Caso peggiore spazialmente	$O(|V|+|E|)=O(b^{d})$
Ottimale	Si (per grafi non ordinati)
Completo	Si

Algoritmo

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 a trovare il nodo cercato. In altre parole, se il nodo cercato non viene trovato, la ricerca procede in maniera esaustiva su tutti i nodi del grafo. Questo algoritmo non è di tipo euristico.

Il procedimento da seguire per metterlo in pratica è sintetizzato come segue:

1. Mettere in coda il nodo sorgente.
2. Togliere dalla coda un nodo (nella prima iterazione il nodo sorgente) ed esaminarlo.
   • Se l'elemento cercato è trovato in questo nodo viene restituito il risultato e la ricerca si interrompe.
   • Se l'elemento cercato non era in questo nodo mettere in coda tutti i successori non ancora visitati del nodo in analisi.
3. Se la coda è vuota, ogni nodo nel grafo è stato visitato e l'elemento non è stato trovato perché non presente e quindi la ricerca si interrompe.
4. Se la coda non è vuota, ripetere il passo 2.

Se si volesse restituire l'albero breadth-first sarebbe necessario tenere nota di tutti i nodi visitati e del predecessore tramite il quale si è arrivati a loro. A tale scopo, a seconda dello stadio di elaborazione, sarebbe utile marcare i nodi con delle etichette quali "visitato", "in corso di visita" e "non visitato".

Realizzazione

L'algoritmo segue il procedimento descritto nella sezione Algoritmo e per poter essere eseguito e restituire dei risultati necessita dell'uso di alcune strutture dati qui di seguito elencate:

• Lista di adiacenza adj[u] che contiene la lista dei nodi adiacenti al generico nodo 'u'.
• Array stato stato[u] che contiene lo stato ("visitato", "non visitato", "in corso di visita") del generico nodo 'u'.
• Distanza d[u] che contiene la distanza del generico nodo u dal nodo "sorgente".

• 

  Esempio animato di una ricerca in ampiezza. Nero: esplorato, grigio: aggiunto alla coda, verrà esplorato più tardi.

  Array p[u] che contiene il predecessore del nodo 'u' nell'albero BFS.
• Coda Q che contiene i nodi "in corso di visita".

È da notare che, nel caso in cui il grafo sia un albero, esiste un solo percorso per arrivare ad ogni vertice, per cui non è necessario utilizzare p[u] e si può semplificare l'implementazione. Per quanto riguarda le strutture dati restanti è da segnalare che sono indispensabili per un corretto funzionamento dell'algoritmo e che se nelle implementazioni non vengono utilizzate direttamente diventa necessario emularle tramite altre metodiche (es. Nell'implementazione python proposta, il campo "vertice.visitato = TRUE" nel tipo di dato "vertice" equivale ad avere la struttura dati stato[u]).

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".

Pseudocodice

Input: un grafo G e un nodo radice v appartenente a G

1  funzione BFS(G,v):
2      crea coda Q
3      inserisci v in Q
4      marca v
5      while Q non è vuota:
6          t ← Q.toglidallacoda()
7          if t è quello che stavamo cercando:
8              return t
9          for all lati e in G.latiincidenti(t) do
12             u ← G.nodiadiacenti(t,e)
13             if u non è marcato:
14                  marca u
15                  inserisci u in Q
16     return none

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)

C++

Per grafi

list<int> lista[INF];
queue<int> coda;

void bfs(int start) {
    bool checked[INF] = {0};
        
    coda.push(start);
    
    while(!coda.empty()) {
        int corrente = coda.front();
        coda.pop();

        if(checked[corrente] == 0) {
            cout << corrente << ' ';
            
            for(list<int>::iterator it = lista[corrente].begin(); it != lista[corrente].end(); ++it) {
                coda.push(*it);
            }
            
            checked[corrente] = 1;
        }
    }
}

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.

Applicazioni pratiche

Testare grafi bipartiti

Il metodo BFS può essere utilizzato per testare se un grafo è bipartito. La tecnica consiste nell'etichettare in maniera alternata con degli 0 e degli 1 i vertici visitati durante una ricerca. Partendo dal nodo sorgente ed etichettandolo con 0 si procede etichettando con 1 tutti i nodi adiacenti e viceversa per i nodi adiacenti. Se ad ogni passo un vertice ha nodi adiacenti già visitati e marcati con la sua stessa etichetta allora il grafo non è bipartito altrimenti il grafo è bipartito.

Crawler

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à.

Osservazioni

• Diversamente dalla ricerca 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.
• È da notare che se si usasse uno stack invece di una coda si andrebbe a costituire un algoritmo di ricerca in profondità.

Voci correlate

• Grafo
• Coda (informatica)
• Ricerca in profondità

Altri progetti

Altri progetti

• Wikimedia Commons

• Wikimedia Commons contiene immagini o altri file sulla ricerca in ampiezza

Collegamenti esterni

• breadth-first search, su sapere.it, De Agostini.
• (EN) Denis Howe, breadth-first search, in Free On-line Dictionary of Computing. Disponibile con licenza GFDL