Ricerca in ampiezza | |
---|---|
![]() | |
Classe | Algoritmo di ricerca |
Struttura dati | Grafo |
Caso peggiore temporalmente | |
Caso peggiore spazialmente | |
Ottimale | Si (per grafi non ordinati) |
Completo | Si |
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.
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:
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".
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:
È 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".
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
# 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)
# R è la radice
coda = [R]
while coda:
# operazione di dequeue
vertice = coda.pop(0)
# operazione di enqueue su ogni figlio
coda.extend(vertice.figli)
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;
}
}
}
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.
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.
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:
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à.