La Depth First Search¶

Lo scopo della Depth First Search (DFS) è quello di visitare i vertici andando più in profondità possibile, connettendo quanti più nodi possibile nel grafo e ramificando la ricerca quando necessario.

E’ anche possibile che la DFS crei più di un albero. Quando l’algoritmo crea un gruppo di alberi lo chiamiamo foresta depth first. Come la BFS, la DFS fa uso dei collegamenti ai predecessori per costruire l’albero. In più, la DFS fa uso di due variabili in più nella classe Vertex class. Le nuove variabili sono il tempo di scoperta e il tempo di fine. Il tempo di scoperta tiene traccia del numero di passi nell’algoritmo prima che il vertice venga incontrato per la prima volta. Il tempo di fine è il numero di passi nell’algoritmo prima che un vertice venga colorato di nero. Come vedremo, il tempo di scoperta e di fine dei nodi ci danno informazioni utili che possiamo usare in alcuni algoritmi.

Il codice della nostra DFS è mostrato in Listing 5. Dal momento che le due funzioni dfs e la sua funzione ausiliaria dfsvisit usano una variabile per mantenere traccia del tempo tra due chiamate a dfsvisit, scegliamo di implementare il codice come metodi di una classe che eredita dalla classe Graph. Questa implementazione estende la classe graph aggiungendo una variabile time e i due metodi dfs e dfsvisit. Osservando line 11 noteremo che il metodo dfs itera su tutti vertici nel grafo chiamando dfsvisit su nodi che sono bianchi. La ragione per cui iteriamo su tutti i nodi è per essere sicuri che tutti i nodi nel grafo siano stati considerati e nessun vertice sia rimasto fuori dalla foresta che stiamo costruendo. Potrebbe sembrare inusuale vedere l’istruzione for aVertex in self, ma dobbiamo ricordarci che in questo caso self è un’istanza della classe DFSGraph, ed è quindi un grafo con l’abilità di fare una DFS. Iterare infatti sui vertici di una istanza di grafo è naturale.

Listing 5

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

from pythonds.graphs import Graph
class DFSGraph(Graph):
    def __init__(self):
        super().__init__()
        self.time = 0

    def dfs(self):
        for aVertex in self:
            aVertex.setColor('white')
            aVertex.setPred(-1)
        for aVertex in self:
            if aVertex.getColor() == 'white':
                self.dfsvisit(aVertex)

    def dfsvisit(self,startVertex):
        startVertex.setColor('gray')
        self.time += 1
        startVertex.setDiscovery(self.time)
        for nextVertex in startVertex.getConnections():
            if nextVertex.getColor() == 'white':
                nextVertex.setPred(startVertex)
                self.dfsvisit(nextVertex)
        startVertex.setColor('black')
        self.time += 1
        startVertex.setFinish(self.time)

Anche se la nostra implementazione della BFS era solamente interessata a considerare nodi per cui c’è un cammino dalla radice ai vertici, è possibile creare una foresta breadth first che rappresenta i cammini più corti tra tutte le coppie di nodi nel grafo. Lo lasciamo come esercizio.

Il metodo dfsvisit comincia con un vertice comincia con un singolo vertice chiamato startVertex e esplora tutti i vicini bianchi in profondità più possibile. Se osserviamo attentamente il codice di dfsvisit e lo confrontiamo con quello della BFS, notiamo che l’algoritmo dfsvisit è quasi identico a bfs eccetto per il fatto che sull’ultima linea del ciclo interno for, dfsvisit chiama sé stesso ricorsivamente per continuare la ricerca a livelli più profondi, mentre bfs aggiunge il nodo a una coda per una esplorazione futura. E’ interessante notare che dove la bfs usa una coda, la dfsvisit usa una pila. Non vediamo la pila nel codice ma è implicita nella chiamata ricorsiva a dfsvisit.

La seguente sequenza di figure mostra l’algoritmo di DFS in azione per un piccolo grafo. In queste figure, le linee tratteggiate indicano archi che sono stati controllati e il nodo dall’altra parte dell’arco è stato già aggiunto all’albero DFS. Nel codice questo test è fatto controllando che il colore di ogni nodo non sia bianco.

La ricerca comincia a un vertice A del grafo (Figura 14). Dal momento che tutti i vertici sono bianchi all’inizio della ricerca, l’algoritmo visita il vertice A. Il primo passo quando il vertice viene visitato è impostare il suo colore a grigio, indicando dunque che il vertice è stato esplorato, e il tempo di scoperta viene fissato a 1. Visto che il vertice A ha due vicini (B, D), ciascuno di loro deve essere visitato. Scegliamo arbitrariamente quale dei due visitare, scegliendo in ordine alfabetico.

Il vertice B è il prossimo vertice visitato (Figura 15), per cui il suo colore è impostato a grigio e il suo tempo di scoperta è impostato a 2. Il vertice B è adiacente a (C, D) per cui seguendo l’ordine alfabetico, visitiamo prima C.

La visita del vertice C (Figura 16) ci porta alla fine di un primo ramo dell’albero. Dopo aver colorato il nodo di grigio e dopo aver impostato il suo tempo di scoperta a 3, l’algoritmo determina che non ci sono vertici adiacenti a C. Questo significa che abbiamo completato l’esplorazione di C e che quindi il suo colore può diventare nero e il suo tempo di fine può essere impostato a 4. Questo stato della DFS è mostrato in Figura 17.

Dal momento che il vertice C era alla fine di un ramo, possiamo adesso ritornare al vertice B e continuare ad esplorare i nodi vicini di B. L’unico vicino di B in più da esplorare è D, per cui possiamo adesso visitare D (Figura 18) e continuare la ricerca dal vertice D. Il vertice D ci porta velocemente al vertice E (Figura 19). Il vertice E ha due vicini, B e F. Normalmente esploreremmo questi vertici in ordine alfabetico, ma dal momento che B è già colorato di grigio, l’algoritmo riconosce che non deve visitare B (altrimenti farlo comporterebbe un ciclo infinito!). Per cui l’esplorazione continua con F (Figura 20).

Il vertice F ha solamente un vertice adiacente, C, ma dal momento che C è colorato di nero non c’è niente altro da esplorare e l’algoritmo ha raggiunto la fine di un altro ramo. Da questo momento in poi, è possibile vedere che da Figura 21 a Figura 25  che l’algoritmo ritorna indietro sui suoi passi fino al primo nodo, impostando il tempo di fine e colorando il vertice di nero.

Figura 14: Costruzione dell’albero di DFS-10

Figura 15: Costruzione dell’albero di DFS-11

Figura 16: Costruzione dell’albero di DFS-12

Figura 17: Costruzione dell’albero di DFS-13

Figura 18: Costruzione dell’albero di DFS-14

Figura 19: Costruzione dell’albero di DFS-15

Figura 20: Costruzione dell’albero di DFS-16

Figura 21: Costruzione dell’albero di DFS-17

Figura 22: Costruzione dell’albero di DFS-18

Figura 23: Costruzione dell’albero di DFS-19

Figura 24: Costruzione dell’albero di DFS-20

Figura 25: Costruzione dell’albero di DFS-21

I tempi di inizio e fine per ogni nodo permettono di vedere una proprietà chiamata parenthesis property. Questa proprietà si riferisce al fatto che tutti i figli di un nodo nell’albero di DFS hanno un tempo di scoperta più alto rispetto al suo e un tempo di fine più basso rispetto al loro genitore. Figura 26 mostra l’albero DFS costruito dall’algoritmo.

Figura 26: L’albero DFS risultante