Forum Informatica Unict

LAUREA TRIENNALE (D.M. 270/04) => Algoritmi, 9 CFU => Topic started by: m3l0 on 10-07-2013, 19:31:00



Title: Dubbio domanda grafo
Post by: m3l0 on 10-07-2013, 19:31:00
Sia G=(V,E) un grafo orientato con n vertici, dato con una matrice di adiacenza. Si supponga di voler costruire la rappresentazione con liste di adiacenza del grafo. Quanto tempo richiede tale costruzione?

Si intende la costruzione del grafo a partire dal grafo dato con la matrice, oppure si intende la costruzione senza partire dal grafo già rappresentato con la matrice?

O(V+E)
O(E)
O(V^2)
O(VE)


Title: Re:Dubbio domanda grafo
Post by: ɹǝǝuıƃuǝsɹǝʌǝɹ on 11-07-2013, 09:57:49
La risposta corretta è \fs{3}O\({V^2}\), perché in input ti viene data la matrice di adiacenza, che ha dimensione proprio \fs{3}O\({V^2}\) e non puoi fare altro che scorrerla tutta (tutte le celle, riga per riga colonna per colonna :boh).