2023-11-30 - DFS

universitystudyingsubject-2101

2023-11-30

Algoritmi

DFS

Serve per effettuare una visita di un grafo.

Si prende la chiave più piccola e si visita in profondità a partire dal nodo che contiene la suddetta chiave.
I nodi non visitati sono bianchi, quelli per cui la visita è iniziata sono grigi e quelli per cui la visita è terminata sono neri.

Se ci sono nodi isolati (o comunque senza archi che li raggiungono) l’algoritmo continua, sempre a partire dalla chiave più piccola, finché non rimangono più nodi bianchi

Utilizziamo tre array ausiliari, che hanno una cella per ogni nodo del grafo.

inizio visita () “discovery”
fine visita () “finish”
predecessore ()

Il contatore di inizio e fine visita è “condiviso” (l’intersezione è nulla)

Ogni nodo per cui inizia la visita cambia colore in grigio, viene impostato il suo tempo di inizio visita e il suo predecessore.
A ogni nodo che finisce di essere visitato (che è quindi grigio) viene impostato il colore a nero e il suo tempo di fine visita.

Si crea una cosiddetta foresta. Un insieme di alberi dove ogni radice coincide con il nodo iniziale con cui si inizia la DFS.

Classifichiamo gli archi di un grafo in quattro tipi:

• Albero (A): sono tutti gli archi che fanno parte di un albero (della foresta) DFS
• Avanti (F - forward): sono tutti gli archi che uniscono i nodi di un albero DFS con tutti i suoi discendenti
• Indietro (I): l’opposto degli archi in avanti - sono tutti gli archi che uniscono i nodi di un albero DFS con tutti i suoi predecessori
• Attraversamento (C - cross): sono tutti gli archi che connettono due nodi che non sono successori/predecessori l’uno dell’altro, anche tra alberi diversi.

Gli archi albero sono tutti gli archi per i quali il nuovo nodo da visitare è bianco.
Gli archi all’indietro sono tutti gli archi per i quali il nuovo nodo da visitare è grigio. La presenza di un arco di questo tipo implica la presenta di un ciclo all’interno del grafo.
Se il nuovo nodo da visitare è nero, potrebbe trattarsi di un nodo in avanti o un nodo di attraversamento.

Indicheremo con |--A--| la rappresentazione del nodo A attraverso data inizio e data fine .

Non può mai accadere che esistono tempo di inizio e fine di due nodi che non siano contenuti l’uno nell’altro, come ad esempio:

|---A---|
	|---B---|

Il nodo A è un predecessore diretto del nodo B (è presente quindi un nodo albero che unisce A e B)

|---A---|
 |--B--|

Nel seguente esempio, se esiste un arco che unisce i nodi B e C, allora è di attraversamento

|--------A-------|
 |-B-|  |--C--|

In questo caso invece, se esiste un arco che unisce i nodi A e C, allora è in avanti.

|--------A-------|
 |-----B-----|
     |--C--|

Quindi, si confronta il tempo di fine visita del nodo nero da visitare con il tempo di inizio visita del nodo attuale. Se il primo è minore del secondo, si tratta di un nodo di attraversamento, viceversa si tratta di un nodo in avanti.

Ordinamento Topologico

È un ordinamento che si basa sulle dipendenze.
Si effettua una visita DFS.
Si ottengono alberi.
Se nel primo albero ci fosse stato un arco verso il secondo albero, sarebbe stato percorso, quindi non esistono archi che vanno dal primo al secondo albero.
L’ordinamento topologico quindi si può realizzare mettendo le visite DFS degli alberi dall’ultimo al primo (in modo tale da evitare eventuali archi che vanno dal secondo albero al primo, ad esempio)
Si prendono quindi i nodi per ordine di fine visita.

GLOBAL t

DFS(G)
	FOR EACH v IN G.V DO
		COLOR[v] = WHITE
		PI[v] = NULL
	t = 0
	FOR EACH v in G.V DO
		if (COLOR[v] == WHITE) THEN
			DFS-VISIT(v) 

DFS-VISIT(v)
	COLOR[v] = GRAY
	d[v] = t
	t = t + 1
	FOR EACH u IN Adj(v) DO // Adj ritorna i nodi adiacenti a v
		IF (COLOR[u] == WHITE) THEN
			PI[u] = v
			DFS-VISIT(u)
	COLOR[v] = BLACK
	f[v] = t
	t = t + 1
	

Se voglio controllare che un grafo sia aciclico è sufficiente aggiungere un controllo del colore grigio nella DFS-VISIT.

L’esecuzione è lineare, quindi la complessità è .

La DFS serve per

• ordinamento topologico
• rilevamento componenti connesse

La BFS serve per:

• calcolo cammino minimo