LabASD - Visita in profondità (DFS)

Moreno Marzolla moreno.marzolla@unibo.it

Ultimo aggiornamento: 2021-04-13

Realizziamo l'algoritmo di visita in profondità (Depth-First Search, DFS) di un grafo orientato \(G=(V,E)\) con \(n\) nodi e \(m\) archi. La visita in profondità parte da un nodo \(v\) ed esplora tutti i cammini orientati "il più a lungo possibile". Attenzione: la visita in profondità non trova i cammini di lunghezza massima.

In questa pagina è presente una interessante visualizzazione dell'algoritmo DFS mentre esplora un labirinto (che può essere descritto tramite un grafo).

Questa implementazione dell'algoritmo DFS segue quanto descritto nel libro di testo, e visita l'intero grafo. Per ogni nodo \(v\) viene calcolato l'istante discover[v] in cui il nodo viene incontrato per la prima volta, e l'istante finish[v] in cui tutti i nodi raggiungibili da \(v\) sono stati esplorati. Si avrà sempre che discover[v] \(\leq\) finish[v].

Durante la visita ogni nodo viene colorato di bianco, grigio o nero. Tutti i nodi sono inizialmente bianchi, ad indicare che non sono ancora stati visitati. Un nodo raggiunto per la prima volta viene colorato di grigio; un nodo diventa nero quando sono esplorati tutti i nodi da esso raggiungibili.

Sebbene l'algoritmo di visita in profondità possa essere realizzato in modo iterativo con l'uso di una pila (stack), risulta più semplice implementarlo in forma ricorsiva come mostrato sul libro.

Si suggerisce di iniziare ignorando gli array discover[] e finish[]; sarà possibile calcolarne il valore in seguito.

Per compilare:

    gcc -std=c90 -Wall -Wpedantic graph.c dfs.c -o dfs

Per eseguire:

    ./dfs < graph10.in

oppure

    ./dfs graph10.in

File