PDA

Visualizza la versione completa : [JAVA] Inplementare un grafo


Zalex
30-01-2004, 02:56
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

Zalex
30-01-2004, 15:14
allora niente????

anx721
30-01-2004, 17:26
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.

Zalex
30-01-2004, 19:10
grazie mille anx!
avevo gia una mezza idea sulle liste di adiacenza!
credo proprio che utilizzero quell'approccio!
ciao e grazie

Loading