Ultimo aggiornamento: 2024-04-17
Realizzare l’algoritmo di visita in profondità (Depth-First Search, DFS) di un grafo orientato \(G=(V,E)\) con \(n\) nodi e \(m\) archi. Si chiede di realizzare la versione di DFS che esplora l’intero grafo e non solo la componente raggiungibile da un nodo sorgente dato. Cliccando sull’immagine in cima alla pagina è possibile vedere l’algoritmo DFS in azione (fonte).
La visita in profondità parte da ogni nodo non ancora esplorato \(v\), e percorre i cammini “il più a lungo possibile”. Si presti attenzione al fatto che la visita in profondità non trova i cammini di lunghezza massima. 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] < finish[v]. L’istante di apertura discover[v] del primo nodo visitato è 1, in conformità con lo pseudocodice visto a lezione.
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 stati esplorati tutti i nodi da esso raggiungibili.
L’algoritmo DFS può essere espresso sia in forma iterativa che ricorsiva. Tuttavia, consiglio di realizzare la versione ricorsiva perché è più semplice da scrivere.
Per compilare:
gcc -std=c90 -Wall -Wpedantic graph.c dfs.c -o dfsPer eseguire in ambiente Linux/MacOSX:
./dfs graph10.inPer eseguire in ambiente Windows:
.\dfs graph10.in