# Verifica se G è una foresta **URL:** \ **Category:** Algoritmi\ **Created:** [13 Febbraio 2019, 4:28pm UTC](https://forum.olinfo.it/t/verifica-se-g-e-una-foresta/5547 "2019-02-13T16:28:09Z")\ **Posts on this page:** 6\ **Page:** 1
**Author:** ![Federica15](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/f/e9a140/32.png) [@Federica15](https://forum.olinfo.it/u/Federica15)\ **Post date:** [13 Febbraio 2019, 4:28pm UTC](https://forum.olinfo.it/t/verifica-se-g-e-una-foresta/5547/1 "2019-02-13T16:28:09Z")
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! ---
**Author:** ![zJack1342](https://forum.olinfo.it/user_avatar/forum.olinfo.it/zjack1342/32/711_2.png) [@zJack1342](https://forum.olinfo.it/u/zJack1342)\ **Post date:** [13 Febbraio 2019, 5:08pm UTC](https://forum.olinfo.it/t/verifica-se-g-e-una-foresta/5547/2 "2019-02-13T17:08:16Z")
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. ---
**Author:** ![v.bizzarri](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/v/7c8e57/32.png) [@v.bizzarri](https://forum.olinfo.it/u/v.bizzarri)\ **Post date:** [13 Febbraio 2019, 5:08pm UTC](https://forum.olinfo.it/t/verifica-se-g-e-una-foresta/5547/3 "2019-02-13T17:08:39Z")
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? ---
**Author:** ![wil93](https://forum.olinfo.it/user_avatar/forum.olinfo.it/wil93/32/2862_2.png) [@wil93](https://forum.olinfo.it/u/wil93)\ **Post date:** [14 Febbraio 2019, 12:37pm UTC](https://forum.olinfo.it/t/verifica-se-g-e-una-foresta/5547/4 "2019-02-14T12:37:16Z")
> [@Federica15](#): > > Dato un grafo semplice G 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 😄 ---
**Author:** ![wil93](https://forum.olinfo.it/user_avatar/forum.olinfo.it/wil93/32/2862_2.png) [@wil93](https://forum.olinfo.it/u/wil93)\ **Post date:** [14 Febbraio 2019, 12:52pm UTC](https://forum.olinfo.it/t/verifica-se-g-e-una-foresta/5547/5 "2019-02-14T12:52:09Z")
> [@v.bizzarri](#): > > Una foresta di k alberi e M nodi dovrebbe avere M-1-k archi 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_” 😅 ---
**Author:** ![v.bizzarri](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/v/7c8e57/32.png) [@v.bizzarri](https://forum.olinfo.it/u/v.bizzarri)\ **Post date:** [14 Febbraio 2019, 4:51pm UTC](https://forum.olinfo.it/t/verifica-se-g-e-una-foresta/5547/6 "2019-02-14T16:51:07Z")
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.