Grafi e alberi

[marx1]

Debbo riolvere questo esercizio:
Si dia un algoritmo che dato un grafo non diretto e connesso di N vertici ed M archi verifichi se esso ´e un albero.
Ho pensato ad una soluzione ma nn è efficente qualcuno potrebbe aiutarmi.

[kanon4]

Se è un albero, allora ha N vertici e M=N-1 archi, quindi puoi verificarlo contando quanti archi ha.
Ciao

[apatriarca]

Io lavorerei nel seguente modo:

Parti scegliendo un vertice del tuo grafo e lo aggiungi nell'insieme V. A questo punto per ogni arco che parte da un vertice di V verifichi che il secondo vertice dell'arco non appartiene a V. Se appartiene a V allora il grafo non è un un albero (quei due vertici sono già connessi attraverso un altro percorso e quindi si viene a formare un ciclo), in caso contrario aggiungi quel vertice a V. Se finiscono i vertici ma non gli archi oppure se finiscono gli archi ma non i vertici allora non hai un albero. Non so se c'è un metodo migliore.

Edit: Ho appena visto che il grafo è connesso... Allora basta confrontare il numero dei vertici e degli archi come già consigliato.

[marx1]

grazie non avevo pensato alla relazione tra il numero di vertici e archi