salve
non mi è chiaro come mai la visità in profondità ha un costo asintotico pari a Teta(V+E) e invece la visita in ampiezza O(V+E)..
a me pare faccino un inizializzazione dei vertici uguale e poi anche la somma delle lunghezze delle liste di adiacenza è uguale..quindi perchè però una ha Teta() e l altra O() ?
Per me tuttedue O(V).
Non conta il numero di archi, perchè visitando in profondità un grafo, ogni nodo viene visitato solo se non era già stato visitato in precedenza.
In totale ogni nodo viene visitato solo una volta anche se il grafo è denso.
Questo è abbastanza per dire che la complessità è O(V), anche se la dimostrazione formale è un' altra storia.
io però sul libro ho che una è con tetagrande l altro con ogrande.. però non capisco sta differenza..
Permessi di invio
Rispondi quotando