Ricerca in profondità

Ricerca in profondità
Ordine di esplorazione dei nodi
Classe	Algoritmo di ricerca
Struttura dati	Grafo
Caso peggiore temporalmente	${\displaystyle O(|V|+|E|)}$ (per grafi espliciti)[1] ${\displaystyle O(b^{d})}$ (per grafi impliciti)[2]
Caso peggiore spazialmente	${\displaystyle O(|V|)}$ (per grafi espliciti)[3] ${\displaystyle O(b^{d})}$ (per grafi impliciti)[2]
Ottimale	No
Completo	No

Nella teoria dei grafi, la ricerca in profondità (in inglese depth-first search, in acronimo DFS), è un algoritmo di ricerca su alberi e grafi. A differenza della ricerca in ampiezza, ha la caratteristica di essere intrinsecamente ricorsivo.

Definizione

Il nome deriva dal fatto che in un albero, ancora prima di avere visitato i nodi delle prime generazioni, l'algoritmo può ritrovarsi a visitare vertici lontani dalla radice, andando così "in profondità". 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). Possiamo vedere l'algoritmo come una visita in ampiezza in cui invece che una coda utilizziamo una pila (ovvero invece di aggiungere gli elementi nuovi in fondo li aggiungiamo in cima). La strategia di ricerca esplora il grafo andando, in ogni istante dell'esecuzione dell'algoritmo, il più possibile in profondità: gli archi del grafo vengono esplorati a partire dall'ultimo vertice scoperto ${\displaystyle v}$ che abbia ancora degli archi non esplorati uscenti da esso. Una volta terminata l'esplorazione di tutti gli archi non esplorati del vertice ${\displaystyle v}$ si ritorna indietro per esplorare tutti gli archi uscenti a partire dal vertice da cui ${\displaystyle v}$' era stato precedentemente scoperto. Il processo di esplorazione continua fin quando tutti i vertici del grafo non siano stati esplorati. Il sottografo dei predecessori, che viene generato dalla visita in profondità può essere costituito da più alberi: tale sottografo è definito foresta DFS, composta, quindi, da diversi alberi DFS. La ricerca DFS, oltre a generare la foresta DFS marca ogni vertice con ben precise informazioni temporali, in particolar modo aggiorna due etichette per ogni vertice: ${\displaystyle d[v]}$ che registra quando il generico vertice ${\displaystyle v}$ è stato scoperto ed ${\displaystyle f[v]}$ che registra quando è stata esplorata l'intera lista di adiacenza di ${\displaystyle v}$ (ovvero tutti i vertici che sono raggiungibili a partire da esso). I vertici vengono colorati in modo differente a seconda dei casi: white, colore che ogni vertice assume prima del tempo ${\displaystyle d[u]}$, grey tra il tempo ${\displaystyle d[u]}$ ed ${\displaystyle f[u]}$ e black nel seguito. Per ogni vertice ${\displaystyle u}$ vale inoltre ${\displaystyle d[u]<f[u]}$.

Realizzazione

La realizzazione dell'algoritmo consiste di due procedure: una procedura che avvia la ricerca e che si occupa di colorare di white tutti i vertici del grafo, di azzerare il contatore globale del tempo e di selezionare ogni singolo nodo del grafo. Per ogni singolo nodo selezionato si avvia una seconda procedura che ha il compito di effettuare la visita vera e propria.

 DFS(G)
   for each vertex u in V[G] do
     color[u] ← white
     π[u] ← nil
   time ← 0
   for each vertex u in V[G] do
     if color[u] = white
       then DFS-Visit(u)

La procedura per la visita del nodo si occupa di colorare opportunamente tutti i vertici visitati a partire da ${\displaystyle u}$ (i vertici nella lista di adiacenza ${\displaystyle Adj[u]}$), di aggiornare i valori temporali e costruire la foresta DFS.

 DFS-Visit(u)
   color[u] ← grey
   d[u] ← time ← time + 1
   for each vertex v in Adj[u] do
     if color[v] = white then
       π[v] ← u
       DFS-Visit(v)
   color[u] ← black
   f[u] ← time ← time + 1

Complessità

La procedura DFS richiede tempo di esecuzione pari a ${\displaystyle \Theta (V)}$ escluso il tempo per l'esecuzione di DFS-Visit. Quest'ultima procedura è chiamata una volta per ogni vertice ${\displaystyle v}$ e il suo ciclo viene eseguito esattamente ${\displaystyle \left|Adj[v]\right|}$ volte, dunque in totale:

${\displaystyle \sum \left|Adj[v]\right|=\Theta (E)}$

Quindi il tempo complessivo di esecuzione è pari a ${\displaystyle \Theta (V+E)}$.

Ordine

Dovendo effettuare delle operazioni su ogni vertice visitato, l'algoritmo può comportarsi in 3 modi diversi:

• effettua l'operazione, poi richiamare se stesso sui figli (pre-ordine)
• richiamare se stesso sui figli, poi effettuare l'operazione (post-ordine)
• richiamare se stesso su alcuni figli, effettuare l'operazione, richiamare se stesso sui figli rimanenti (visita in ordine, interessante negli alberi binari o in grafi con liste di adiacenza ordinate in modo particolare)

Realizzazione in Python

Per grafi

def visita(vertice):
    vertice.visitato = True
    for adiacente in vertice.adiacenti:
        if not adiacente.visitato:
            visita(adiacente)

Per alberi

def visita(vertice):
    for adiacente in vertice.adiacenti:
        visita(adiacente)

Note

1. Noto il numero di vertici ${\displaystyle |V|}$ e di archi ${\displaystyle |E|}$
2. Noto il branching factor ${\displaystyle b}$ e la profondità massima ${\displaystyle d}$
3. Noto il numero di vertici ${\displaystyle |V|}$

Bibliografia

• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Introduzione agli algoritmi, Jackson Libri, 2003, ISBN 88-256-1421-7.

Voci correlate

• Ricerca in ampiezza
• Backtracking

Altri progetti

Altri progetti

• Wikimedia Commons

• Wikimedia Commons contiene immagini o altri file sulla ricerca in profondità

Collegamenti esterni

• depth-first search, su sapere.it, De Agostini.
• (EN) Eric W. Weisstein, Depth-First Traversal, su MathWorld, Wolfram Research.
• (EN) Depth-first search, su Encyclopaedia of Mathematics, Springer e European Mathematical Society.
• (EN) Denis Howe, depth-first search, in Free On-line Dictionary of Computing. Disponibile con licenza GFDL