Forum Informatica Unict

LAUREA TRIENNALE (D.M. 270/04) => Algoritmi, 9 CFU => Topic started by: RobyP on 19-12-2010, 14:43:47



Title: Domanda grafi
Post by: RobyP on 19-12-2010, 14:43:47
Salve, mi sfugge
1-quale è il tempo per cambiare rappresentazione di un grafo da lista a matrice e viceversa...

2-di conseguenza anche il tempo per costruire un grafo con lista e uno con matrice

(credo che non abbiano a che fare con lo spazio di memoria che occupano rispettivamente)

Grazie per le risposte  :-ciao bye


Title: Re:Domanda grafi
Post by: shiny on 19-12-2010, 19:58:36
io credo che sia O(E)  .ciaociao


Title: Re:Domanda grafi
Post by: RobyP on 19-12-2010, 20:25:44
Ma cosa?


Title: Re:Domanda grafi
Post by: Naive on 19-12-2010, 20:33:43
Io avrei risposto per la prima e per la seconda
da lista a matrice O(V^2) e da matrice a lista O(V+E) ora non so...ho molti dubbi su questa parte...non prendere per certa la mia risposta :(


Title: Re:Domanda grafi
Post by: Crasher on 19-12-2010, 21:56:10
Io avrei risposto per la prima e per la seconda
da lista a matrice O(V^2) e da matrice a lista O(V+E) ora non so...ho molti dubbi su questa parte...non prendere per certa la mia risposta :(
Boh per come la penso io dovrebbe essere al contrario.
Da matrice a lista O(V^2) in quanto dovrà scandire ogni elemento della matrice (quindi 2 for) e inserirlo nella lista (se lo inserirà sempre in testa alla lista richiederà O(1) o sbaglio?)
Da lista a matrice O(E) o O(2E) se è orientato o meno...
8-|


Title: Re:Domanda grafi
Post by: Naive on 19-12-2010, 22:03:32
per la prima hai ragione ho invertito...invece non capisco perchè la seconda ti viene O(E)


Title: Re:Domanda grafi
Post by: Daréios89 on 19-12-2010, 22:26:53
Si forse ha ragione Crasher...in teoria da matrice a lista O(v^2), ma a questo punto da lista a matrice dovrebbe scorrere sia i vertici che la lista di adiacenza, quindi non dovrebbe essere O(V+E) ?


Title: Re:Domanda grafi
Post by: alex180788 on 18-01-2011, 17:58:17
sono daccordo... più precisamente |V| per scorrere la lista e 2|E| per visitare tutte le liste delle adiacenze quindi |V|+ 2|E| =O (|V|+|E|)
credo che daréios abbia fatto questo ragionamento