Implementare una Breadth First Search¶

Breadth first search (BFS) è uno degli algoritmi fondamentali per risolvere molti problemi.

Dato un grafo \(G\) e un vertice di partenza \(s\), una BFS procede esplorando gli archi in un grafo per trovare tutti i vertici in \(G\) per cui c’è un cammino da \(s\). La proprietà importante di una BFS è che trova tutti i vertici che sono a distanza \(k\) da \(s\) prima di trovare gli altri vertici che sono a distanza \(k+1\). Un buon modo di vedere la cosa è immaginare che la BFS costruisca un albero, un livello dell’albero alla volta. Una BFS aggiunge tutti i figli al vertice di partenza prima che cominci a scoprire qualsiasi degli altri nipoti.

Per tenere traccia di questo progresso, la BFS colora tutti i vertici di bianco, grigio, o nero. Tutti i vertici sono inizializzati bianchi all’inizio. Un vertice bianco è un vertice non ancora scoperto. Quando un vertice viene scoperto è colorato di grigio e quando la BFS ha completamente esplorato il vertice lo colora di nero. Questo significa che una volta che un vertice è stato colorato di nero, non ha più vicini bianchi. Mentre invece un nodo grigio potrebbe avere ancora vertici bianchi adiacenti, che vuol dire che ci sono ancora suoi vicini da esplorare.

L’algoritmo di BFS mostrato in Listing 2 sotto usa il grafo che abbiamo implementato prima. In più, usa una Queue, coda in italiano, un punto cruciale per decidere quale prossimo vertice esplorare.

Inoltre, BFS usa una versione estesa della classe Vertex. Questa nuova classe aggiunge tre nuove variabili: distance, predecessor e color. Ciascuna di queste variabili ha anche appropriati metodi getter e setter. Il codice per questa versione estesa è inclusi nel pacchetto pythonds, ma non è mostrato qui perché l’unica differenza è la presenza di queste nuove variabili.

La BFS comincia al vertice di partenza s e colora start grigio per mostrare che viene correntemente esplorato. Altri due valori, la distanza e il predecessore sono rispettivamente inizializzati a 0 e None per il vertice di partenza. Dunque, start viene messo nella Queue. Il prossimo passo è cominciare sistematicamente a esplorare vertici in testa alla coda, ovvero quelli che sono stati inseriti prima nella coda vengono estratti prima (secondo la politica FIFO: first in first out). Esploriamo il nuovo nodo in testa alla coda e iteriamo sulla sua lista di adiacenza. Ogni volta che un nodo della lista di adiacenza viene esaminato, controlliamo il suo colore. Se è bianco, il vertice non è esplorato e le seguenti quattro cose succedono:

1. Il nuovo vertice non esplorato nbr viene colorato grigio.
2. Il predecessore di nbr viene impostato come currentVert
3. La distanza di nbr viene impostato come quella di currentVert + 1
4. nbr è aggiunto alla fine della coda. Aggiungere nbr alla fine della coda fa prenotare questo nodo per una futura esplorazione, ma non prima che tutti gli altri vertici della lista di adiacenza di currentVert sono stati esplorati.

Listing 2

from pythonds.graphs import Graph, Vertex
from pythonds.basic import Queue

def bfs(g,start):
  start.setDistance(0)
  start.setPred(None)
  vertQueue = Queue()
  vertQueue.enqueue(start)
  while (vertQueue.size() > 0):
    currentVert = vertQueue.dequeue()
    for nbr in currentVert.getConnections():
      if (nbr.getColor() == 'white'):
        nbr.setColor('gray')
        nbr.setDistance(currentVert.getDistance() + 1)
        nbr.setPred(currentVert)
        vertQueue.enqueue(nbr)
    currentVert.setColor('black')

Vediamo come la funzione bfs costruirebbe l’albero BFS corrispondente al grafo in Figura 4.

Figura 4: Grafo di esempio

Partendo da fool, consideriamo tutti i nodi che sono adiacenti a fool e aggiungiamo loro all’albero. I nodi adiacenti includono pool, foil, foul e cool. Ognuno di questi nodi è aggiunto alla coda dei nuovi nodi da espandere. Figura 5 mostra l’evoluzione dell’albero con la coda dopo questo passo.

Figura 5: Il primo passo della BFS

Al prossimo passo, bfs rimuove il prossimo nodo (pool) dalla testa della coda e ripete il processo per tutti i nodi adiacenti. Tuttavia, quando bfs esamina il nodo cool, trova che il colore di cool è stato già cambiato in grigio. Questo indica che c’è un cammino più corto per arrivare a cool e che cool è già sulla coda per la futura visita. L’unico nuovo nodo aggiunto alla coda mentre esaminiamo pool è poll. Il nuovo stato dell’albero e della coda è mostrato in Figura 6.

Figura 6: Il secondo passo della BFS

Il prossimo vertice della coda è foil. L’unico nuovo nodo che foil può aggiungere all’albero è fail. Mentre bfs continua a processare la coda, nessuno dei prossimi due nodi aggiunge niente di nuovo all’albero e alla coda. Figura 7 mostra l’albero e la coda dopo l’espansione di tutti i vertici sul secondo livello dell’albero.

Figura 7: Albero di BFS dopo aver completato un livello

FIgura 8: Albero BFS finale

Figura 8 mostra l’albero finale di BFS dopo che tutti i vertici in Figura 4 sono stati visitati.

Possiamo cominciare da ogni vertice nell’albero di BFS e seguire le frecce all’indietro verso la radice per trovare il cammino di minima lunghezza dalla radice al vertice. La funzione sotto (Listing 3) mostra come farlo, seguendo i collegamenti al predecessore.

Listing 3

def traverse(y):
    x = y
    while (x.getPred()):
        print(x.getId())
        x = x.getPred()
    print(x.getId())

traverse(g.getVertex('sage'))