Visita in ampiezza

Nel trattamento di grafi (ed in particolare alberi), si intende per visita per ampiezza uno dei metodi per "scorrere" tutti i nodi di un grafo in sequenza.

Diversamente dalla visita in profondità per i grafi e dalle sue varianti (pre-ordine, ordine, post-ordine) sugli alberi, la visita in ampiezza non può essere implementata 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 (in un albero, sarà la radice) nella coda 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.

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.

Se fatto girare su un albero, l'algoritmo porta a visitare un livello gerarchico alla volta in tutta la sua larghezza; da qui il nome. Non a caso, se fatto girare su un grafo, l'algoritmo individua un albero che ne è un sottografo (ovvero che ne contiene tutti i vertici e tutti e soli gli archi che sono stati seguiti).

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

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

Codice 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

• Visita in profondità
• Coda