Ciao a tutti ragazzi! Ho questo problema:
Dato un grafo semplice G, progettare un algoritmo che determini se G è una foresta.
Data la definizione di foresta, ovvero un grafo non orientato e aciclico, devo verificare quindi che G non ha cicli e che G non è orientato. Per verificare se a o meno cicli posso effettuare una DFS, ma per verificare che non è orientato come posso fare?
Avete una soluzione migliore a quella che ho pensato?
Grazie a tutti per l’aiuto!
Una foresta è un insieme di alberi, quindi per ogni componente del grafo devi verificare che sia un albero.
Una componente è un albero se non contiene cicli e il numero di archi sia uguale al numero dei nodi - 1.
Per verificare che il grafo non è direzionato mi verebbe in mente di controllare che tra gli archi dati in input non ci sia una coppia che rappresenti lo stesso arco ma con i nodi invertiti.
Non avendo idea sulle dimensioni massime del grafo direi che il caso peggiore sia O( E *log(E) ) dove E rappresente il numero di archi.
Per la verifica dei cicli basta utilizzare una dfs come hai proposto.
Nella dfs devi solo preoccuparti che se puoi visitare un nodo già visitato che non sia il padre non hai un albero.
Mentre per gli archi un semplice set in cui inserisci la coppia di archi tenendo il primo elemento minore del secondo.
Un paio di considerazioni che potrebbero tornare utili:
Un albero di N nodi ha N-1 archi.
Una foresta di k alberi e M nodi dovrebbe avere M-1-k archi.
Se per visitare tutti i nodi servono k dfs cosa si può concludere?
Per assunzione ti viene detto che G è un grafo semplice, ovvero “un grafo non diretto che non comprende cappi e archi multipli”.
Quindi a mio avviso direi che non serve verificare che non sia diretto. Lo sai per ipotesi del testo 
A occhio direi che il numero di archi può variare tra un minimo di M-k, quando i k alberi sono tutti “separati”, fino a un massimo di M-1, quando gli alberi sono tutti connessi tra di loro (e la foresta “collassa” e diventa essa stessa un albero).
EDIT: ah, ma sicuramente sottintendevi “una foresta di k alberi separati” 
Si intendevo k alberi separati, avrei fatto meglio a specificarlo ma la mia terminologia è quella che è.
Comunque, premesso che da qui in poi per albero intendo albero separato, la mia idea era la seguente:
Partendo da un unico albero di N vertici (e quindi N-1 archi) se tolgo un arco verrò ad avere due alberi e così via ogni volta che tolgo un arco aumenta di una unità il numero degli alberi.
Quindi una foresta di k alberi avrà N-k-1 archi.
Tenuto presente che una DFS a partire da un vertice non visitato visita tutti i vertici di uno stesso albero ma non quelli degli altri …
P.S. Considero come albero anche un vertice isolato.