[GRAFi]!! Molto urgente!!

[dungedra]

Mi potreste spiegare la differenza tra grafi densi e sparsi???

ed inoltre, cosa ancor piu importante come funziona piu o meno l'implementazione dell'algoritmo di prim e di djikstra con l'heap indicizzato???
Per sommi capi me lo potreste dire, ho solo capito che considerano i pesi del grafo come le priorità di una coda implementata a heap, la quale ,tramite l'heap, rimuove quelli con priorità massima e poi successivamente come per l'algoritmo di prim, li va ad inserire (gli archi con quella priorità) in un nuovo albero..è giusto??

Inoltre so che è preferibile implementare con l'heap e non con i vettori, perche abbasso i costi a theta(m*logn), sia che si abbia a che fare con grafi densi, o con grafi sparsi....

[vict85]

Hai provato a leggerti queste cose su wiki prima di postare sul forum? Cosa non ti è chiaro su quello che c'é scritto lì?

[Nich999]

Mi potreste spiegare la differenza tra grafi densi e sparsi???

Praticamente un grafo è sparso se il numero di archi che si dipartono da un generico nodo è costante o comunque indipendente dal numero dei nodi del grafo.
Un grafo è denso invece se il numero di archi che si dipartono da un generico nodo è una funzione lineare del numero dei vertici.
Formalmente:
grafo G(V,E) denso se : |E| = O(|V|^2). Esempio da ogni nodo si dipartono |V| archi(Grafo completo)
grafo G(V,E) sparso se : |E| = O(|V|). Esempio da ogni nodo si dipartono k archi(Bounded Valence Graph)

ed inoltre, cosa ancor piu importante come funziona piu o meno l'implementazione dell'algoritmo di prim e di djikstra con l'heap indicizzato???
Per sommi capi me lo potreste dire, ho solo capito che considerano i pesi del grafo come le priorità di una coda implementata a heap, la quale ,tramite l'heap, rimuove quelli con priorità massima e poi successivamente come per l'algoritmo di prim, li va ad inserire (gli archi con quella priorità) in un nuovo albero..è giusto??

Sia Dijkstra che Primm usano come struttura dati di appoggio una Priority Queue implementata tramite Min-Heap.
Nel caso di Dijkstra la priorità di un nodo rappresenta la stima del percorso a costo minimo per raggiungere il nodo, che si dimostra convergere al cammino minimo quando il nodo viene estratto dalla coda.
Nel caso di Primm la priorità di un nodo rappresenta il costo per raggiungere il nodo da uno dei suio vertici adiacenti che si trova già nell'albero di copertura minima. In pratica è il costo dell'arco leggero.

Spero di esserti stato d'aiuto.