Re: il grafo, di cui si diceva

beccoblu wrote:

> grazie a tutti. kruskal credo che sia il mio uomo :-)

Se quello che cercavi era l'MST (minimo albero ricoprente) allora
l'algoritmo più semplice in assoluto è l'algoritmo di Prim con matrice
di adiacenza, che ha complessità (di tempo) quadratica nel numero dei nodi.

Kruskal potrebbe essere un po' più efficiente, ma non nel tuo caso
particolare di grafo completo(*), per cui io userei Prim senza pensarci
un attimo.
Demo:
http://www-b2.is.tokushima-u.ac.jp/~ikeda/suuri/dijkstra/Prim.shtml

(*)
Ma la completezza del grafo in input è veramente data o è una cosa che
hai dedotto tu dal fatto che i nodi sono sul piano euclideo ed hai
pensato che andassero calcolate tutte le distanze?
Perché se ti trovi in quest'ultimo caso (piano euclideo), non serve il
calcolo di tutte le distanze, ma solo della cosiddetta /triangolazione
di Delaunay/, essendo l'MST un suo sottinsieme:
http://en.wikipedia.org/wiki/Delaunay_triangulation

Una volta calcolata la triangolazione (che si calcola in O(n log n) dove
n è il numero di nodi), puoi applicarvi sopra Kruskal ottenendo in
effetti un vantaggio (asintotico) rispetto a Prim con matrice di
adiacenza. (Ma ovviamente è più complesso da implementare.)

P.S.
Recentemente è stato inventato un algoritmo per l'MST che sembra essere
il più veloce in assoluto (asintoticamente), basato sul cosiddetto
soft-heap:
http://portal.acm.org/citation.cfm?doid55541.355554

ma dubito che ti convenga impelagartici.

Ciao.
[ Auf dieses Posting antworten ]