Newsgroup: it.comp.java
Titolo: Rappresentazione grafo

Buongiorno a tutti,
vorrei chiedere un consiglio: che struttura dati utilizzare per la
rappresentazione di un grafo (nodi e archi)?
Grazie,
Fausto Mancini

Non vorrei dirti stupidate, ma a me non sembra che esistano già classi delle
API pronte a questo. Comunque potresti crearle tu: se non ti servono gli
archi (nel senso che non devi ad esempio tenere conto di valori degli
archi), ma ti servono solo i nodi, allora ti crei una classe Nodo che al suo
interno possiede una LinkedList o un Vector, nel quale vai a metterci altri
nodi.
Se hai bisogno anche di rappresentare l'arco che connette due nodi, bhè
basta che la tua classe nodo abbia anche una lista o un vettore di campi
"peso" che equivalgono alle lunghezze degli archi di collegamento tra il
nodo e gli altri nodi a cui è collegato. Magari pensandoci sopra un pochetto
puoi migliorare notevolmente questi concetti!!
Ciao!

 wrote in message
news:aveb0s$447$1...@monty.lombardiacom.it...

Ti ringrazio.
Per adesso la mia soluzione è simile a quella che mi consigli:
- la classe nodo
- la classe arco
Entrambe le classi hanno i fields:
- String name
- Vector children
Il vettore children contiene il nome dei figli (il field name delle due
classi).
Pensavo quindi di gestire la struttura del grafo con una bella HashMap (key:
name).
Elegante, no?
Altri pareri?
Fausto.

 rappresentazione di un grafo (nodi e archi)?
Dipende da cosa ci devi fare. Spesso si usano matrici.
-- 
Life's something u don't get out alive..
ObjectZone - 
http://space.tin.it/computer/csadun

 ha scritto nel messaggio
news:avec2e$eiv37$1...@ID-121868.news.dfncis.de...


 rappresentazione di un grafo (nodi e archi)?
Diversi anni fa (una quindicina) per rappresentare grafi (tesi di 
ingegneria) in c ho usato delle matrici.
Stefano

 wrote in message
news:Xns92FC844C5AF2Ecr...@130.133.1.4...

Grazie, avevo già studiato (e dimenticato) la rappresentazione matriciale...
Ma non sono sicuro che sia la migliore per ciò che devo fare. Vaglierò...
Fausto


A livello teorico, le soluzioni piu' gettonate sono le "liste di 
adiacenza" oppure le "matrici di adiacenza".
Liste di adiacenza:
0: 1 -> 2 ->NULL
1: 3 -> NULL
2: NULL
3: 4 -> 5 -> 6 -> NULL
4: NULL
5: NULL
6: NULL
Ossia ad ogni vertice associ tutti i figli. questo qua sopra e' anche un 
albero (oltre ad essere un grafo orientato)
Matrice di adiacenza equivalente:
   0 1 2 3 4 5 6
0   1 1
1       1
3         1 1 1
4
5
6
Equivalente alla rap. di cui sopra. Questa fa vedere molto velocemente 
chi e' il padre di chi, ma puo' sprecare spazio nel caso di grafi grandi 
e con relativamente pochi archi.
Puoi sostituire gli uno con eventuali valori dei pesi (con le liste di 
adiacenza ovviamente metti tutto nelle strutture dei nodi), in questo 
caso devi avere un valore univoco per "assenza di arco" (che nella 
matrice sopra e' 0, ma ho omesso di scrivere)
HTH,
uL

 adiacenza" oppure le "matrici di adiacenza".
[cut]

 La cosa si fa interessante...
Se l'ha gia' scritto (non ho verificato, so che lo stava preparando), 
comprati il Sedgewick sui grafi con implementazione in Java (ce n'e' uno 
in C ed uno in C++) per avere sottomano tutto lo scibile relativo
uL

"ugo" <ugo.l...@sun.COM> wrote in message
news:avf02b$a8r$1...@new-usenet.uk.sun.com...

L'ho cercato... ma non è ancora pronto: "(Algorithms in Java, Part 5 (Graph
Algorithms), to appear in early 2003 )"

 Algorithms), to appear in early 2003 )"
Nel frattempo allora comprati quello sul C ;)
La teoria e' la stessa, al limite devi riadattare il codice. E se lo fai 
in C, poi in Java diventa una passeggiata: l'unico problema e' che 
magari ti perdi qualche cosa di gia' pronto nelle librerie.
Per le Collection API, invece, leggiti il tutorial di Sun e i vari 
articoli di Zukowski (c'e' anche in giro un suo ottimo libro)
ciao
uL



In "Data Structures and Algorithms in Java" - Goodrich & Tamassia, il
capitolo 12 e' dedicato proprio ai grafi. Sono in tutto una settantina di
pagine, ma presenta le principali tecniche di implementazione dei grafi e
qualche utile algoritmo (ad esempio il classico algoritmo di Dijkstra).
-- 
Lucio Benfante
Brainbench MVP for Java 1
http://www.brainbench.com
MyTranscript: 
http://www.brainbench.com/transcript.jsp?pid=167064

 rappresentazione di un grafo (nodi e archi)?
Prova a cercare su 
http://sourceforge.net
 io li ho trovato classi gia fatte.
-- 
Magellano


Prova con "Adam Drozdek" "Algoritmi e strutture dati in Java". L'ho 
usato con ottimi risultati per preparare lo scritto di Informatica 2.