Creare un grafo in Java

[One2]

Come da titolo,vorrei sapere come posso creare una classe che realizzi un grafo,sono alle prime armi con il Java e mi sarebbe immensamente utile se qualcuno mi indicasse dei siti dove posso trovare qualche esempio di algoritmo sulla costruzione dei grafi fatto bene

[Pierpaoli1]

Per grafo intendi una lista linkata? se è quello cerca java.util.List ciao

[apatriarca]

Esistono diversi modi per implementare un grafo, puoi rappresentare i nodi come oggetti e avere una lista di nodi collegati ad ogni nodo, oppure avere una lista di oggetti e una di archi, oppure avere una matrice che rappresenta le adiacenze tra i vari nodi. Che cosa hai in mente? Che cosa devi fare con questo grafo? Che cosa devi rappresentare?

[One2]

"Pierpaoli":Per grafo intendi una lista linkata? se è quello cerca java.util.List ciao

Ok,credo possa andare bene.Ora mi servirebbero,se possibile,esempi degli algoritmi per calcolare il "minimum spanning tree" e lo "shortest path" di un grafo.(Vanno bene anche esempi incompleti,giusto per capire un po come funziona l'algoritmo)

[Pierpaoli1]

se mi spieghi cosa vuol dire minimum spanning tree e shortest path magari posso anche aiutarti . Ciao

[apatriarca]

Anche se una lista può essere analizzata come un grafo, un grafo non è in generale una lista. Un grafo ha in generale una struttura MOLTO più complessa. Il minimum spanning tree in una lista è semplicemente la lista stessa e la distanza minima è semplicemente la sottolista che inizia da uno dei due nodi e finisce nell'altro. Non è certamente un grafo molto interessante da considerare. Per rappresentare grafi più generali si fa ricorso a strutture dati diverse a secondo dell'uso. Ripeto quindi la domanda: come sono definiti i grafi negli algoritmi che vuoi imparare?

Una libreria in Java per la gestione dei grafi è JGraphT.

[One2]

Provo,spero di essere chiaro,a definire il tipo di grafo che mi serve:
Nel mio caso i grafi devono essere definiti come una quaterna $(Nodo,Arco,Lab1,Lab2)$
Dove Nodo è un sottoinsieme finito di nodi.
Arco è un sottoinsieme di coppie di elementi di Nodi
Lab1 è una funzione del tipo Nodi->Inf,e Lab2 è una funzione del tipo Arco->Cost.(Cost=Insieme delle possibili etichette sugli archi).

[apatriarca]

Che cosa è Inf?

[One2]

"apatriarca":Che cosa è Inf?

Inf E' un nodo che contiene le informazioni....
Comunque,aiutandomi con il libro,sono riuscito a creare l'algoritmo.
Ora mi servirebbe capire come funziona un'algoritmo che determini lo SpanningTree del grafo

P.S:Non sò se aprire un topic apposito...

[apatriarca]

Hai provato a cercare su internet? Esistono diversi algoritmi per calcolare il MST. I più semplici sono [url=http://en.wikipedia.org/wiki/Borůvka's_algorithm]l'algoritmo di Borůvka[/url], [url=http://en.wikipedia.org/wiki/Prim's_algorithm]l'algoritmo di Prim[/url], [url=http://en.wikipedia.org/wiki/Kruskal's_algorithm]quello di Kruskal[/url] e il Reverse-Delete algorithm. Ce ne sono poi di più complicati, ma direi che puoi iniziare da uno di questi.