Salve raga,
devo implementare un grafo e vorrei qualche parere o consiglio....
io avevo pensato a un cosa del genere:
classe Vertice{
nomeVertice
}
classe Arco{
Vertice verticePartenza
Vertice verticeArrivo
Int peso
}
classe Grafo{
listaArchi
listaVertici
}
che ne dite?
altre idee?
Dimenticavo: devo farlo in Java.
grazie
ciao
allora niente????
La scelta della struttura dati migliore in genere dipende dal tipo di operazioni che dovrai eseguire sulla struttura.
La tua implemetazione, sebbene corretta non è la più adatta nell'eseguire le operazioni piu semplici che si fanno sui grafi, come ad esempio trovare i vertici adiacenti ad un certo vertice v o effettuare una visita del grafo.
Per i grafi sono state proposte diverse forme di rappresentazioni, le piu classiche sono:
Matrice di Adiacenza:
Se il grafo G ha n vertici, si associano i vertici ai primi n numeri interi e si rappresenta il grafo con una matrice quadrata M di zeri e uni e di dimensione n x n , tale che M(i, j) = 1 se esiste l'arco che connette il vertice i e il vertice j. Se il grafo è pesato e i pesi sono >= 0, puoi sostituire gli zeri con un numero negativo e gli uni con il peso dell'arco asociato a quell'elemento della matrice.
Matrice di incidenza:
Se il grafo ha n vertici e m archi, si associano i vertici ai primi n numeri e gli archi ai primi m numeri e si rappresenta il grafo con una matrice M di zeri e di uni e di dimensione m x n, tale che M(i, j) = 1 se e l'arco i incide sul vertice j. Per i pesi vale quanto detto sopra.
Liste di adiacenza:
Per ogni vertice v del grafo si costruisce una lista di vertici, che rapprsenta l'insieme dei vertici a cui v è adiacente. Il grafo è quindi rappresentato mediante una lista di liste, tante quanti sono i vertici, ognuna delle quali rapresenta la lista di adiacenza di un vertice. Se il grafo e pesato, gli elementi della lista di vertici devono contenere oltre al nome del vertice anche il peso.
Nei primi due casi, in java, puoi definire una classe che contiene un campo che mantiene la matrice come array bidimensionale; nel terzo caso puoi implementare una classe per rappresentare la lista di vertici:
class VertexList{
int vertex;
int weight; //il peso dell'arco
VertexList next; //l'elemento successivo nella lista
}
o definire solo vertex e weight e realizzare la lista con una classe già definita nel linguaggio java.
Ciao.
grazie mille anx!
avevo gia una mezza idea sulle liste di adiacenza!
credo proprio che utilizzero quell'approccio!
ciao e grazie
Permessi di invio
Rispondi quotando