View Full Version : ricostruire/disegnare un grafo da questi dati...
questi sono i dati di un grafo in un file testo:
NODI 07 LINK 13 PARTENZA 02 ARRIVO 04
2 1 7.00
2 3 1.00
3 1 3.00
3 5 4.00
3 6 3.00
1 5 2.00
1 4 8.00
4 5 1.00
5 7 2.00
6 5 4.00
6 7 7.00
7 4 2.00
6 4 10.0
vorrei ricostruire graficamente anche in asciiart il grafo per capire come è fatto per poi cercare di buttare giù un mio algopritmo... però devo sapere ha cosa corrisponde la 1° e la 2° colonna... la 3° colonna è evidente che sono i pesi.
La 2° colonna corrisponde ai nodi (vediamo se è giusto questo)
2 2 primo nodo
3 3 3 secondo nodo
1 1 terzo nodo
4 quarto nodo
5 quinto nodo
6 6 6 sesto nodo
7 settimo nodo
come sono disegnati i nodi su carta e i 13 Link che li legano??
La seconda colonna proprio non riesco a capirla... sono i link... in asciiart sarebbe tipo:
o=nodo
----= link
o---o (nodo 1 link e nodo 2)...
posso leggere questo file testo naturalmente ma se qualcuno mi aiuta a capire (a farmi vedere graficamente il grafo) così che capisco meglio come è strutturato tramite un disegno.
Niente non riesco a capacitarmi di come è connessa la prima e la seconda colonna...
sottovento
26-02-2007, 12:26
Ciao,
scusa, forse non ho capito bene. Mi sembrerebbe piu' facile, avendo tre colonne a disposizione, che la prima indichi il nodo di partenza, la seconda il nodo di arrivo e la terza il peso dell'arco.
Perche' questa interpretazione non va bene?
Per quanto riguarda la sua rappresentazione grafica, su sourceforge c'e' un progettino in Java, molto semplice da usare, che ti permette di plottare alberi (sono sicuro) e grafi (un po' meno sicuro) in maniera semplicissima. Penso che se plotta i grafi hai il 95% del codice gia' fatto.
Se mi viene in mente il nome del progetto, posto un altro commento qui.
Ciao
Ciao,
scusa, forse non ho capito bene. Mi sembrerebbe piu' facile, avendo tre colonne a disposizione, che la prima indichi il nodo di partenza, la seconda il nodo di arrivo e la terza il peso dell'arco.
Perche' questa interpretazione non va bene?
Per quanto riguarda la sua rappresentazione grafica, su sourceforge c'e' un progettino in Java, molto semplice da usare, che ti permette di plottare alberi (sono sicuro) e grafi (un po' meno sicuro) in maniera semplicissima. Penso che se plotta i grafi hai il 95% del codice gia' fatto.
Se mi viene in mente il nome del progetto, posto un altro commento qui.
Ciao
Il problema è che mi sono avvicinato ora a Dijkstra...
ora questo è il link che mi ha postato cionci:
http://it.wikipedia.org/wiki/Algoritmo_di_Dijkstra
come puoi vedere c'è il disegno del grafo (anche se non riesco a costruire un algoritmo per ora...)
mentre ho questa tabella file testo che indica appunto un grafo ma non il disegno...
posso aggiungere:
ho 2 matrici grafo che contiene la tabella letta da file testo come detto
nel primo
post e mix che a le righe e le colonne inizializzate a infinito = 999
questo è il commento per capire il tutto in cui io non riesco a capirlo!
grafo: matrice LINK X 3 colonne letta da file di input (grafo.txt);
col0=nodo-coda, col1=nodo-testa, col2=peso.
mix: matrice NODI+1 X 3 colonne usata per tener traccia delle etichette.
Le righe rappresentano i vertici;
col0=distanza tra il vertice della riga e quello di partenza;
col1=vertice precedente;
col2=etichetta (1=si, 0=no).
mi dovrebbe rispondere cionci... ma se qualcuno sà come interpretare la tabella... io sarei molto grado!
il nodo di partenza è 2 e l'arrivo è il 4.
poi
k=partenza; //partenza
i=0;
mix[0][2]=0; //per evitare problemi con la funzione trova_minimo.
mix[k][0]=0; //nella colonna 0 c'è la distanza tra il
//vertice attuale e quello di partenza.
mix[k][1]=k; //nella colonna 1 ci sono i vertici precedenti.
mix[k][2]=1; //nella colonna 2 ci sono i flag 1 o 0 che indicano
//se un nodo è stato etichettato.
In definitiva vedendo il disegno del link di cionci un idea me la sono fatta ma vedendo il file testo postato (di cui non c'è il disegno del grafo) volevo appunto ricostruire il disegno per capire come era fatto questo benedetto grafo e capire appunto la 1° e la 2° colonna... perchè proprio non l'ho capite!
col0 col1 col-pesi
2 1 7.00
2 3 1.00
3 1 3.00
3 5 4.00
3 6 3.00
1 5 2.00
1 4 8.00
4 5 1.00
5 7 2.00
6 5 4.00
6 7 7.00
7 4 2.00
6 4 10.0
colonna 0=nodo-coda
colonna 1=nodo-testa
cosa è nodo-coda e nodo testa?
cionci mi hai passato questo link:
http://it.wikipedia.org/wiki/Algoritmo_di_Dijkstra
ebbene su questo grafo ho costruito la tabella che è questa:
NODI 07 LINK 9 PARTENZA 01 ARRIVO 07
1 2 2.00
1 3 6.00
2 4 2.00
2 5 8.00
3 4 2.00
3 6 3.00
4 6 4.00
7 5 8.00
6 7 9.00
il risultato è:
7 6 4 2 1
1--> 2--> 4--> 6--> 7
mentre dovrebbe essere
1--> 2--> 4--> 3--> 6--> 7
il code è OK.
guarda un pò se ho sbagliato a dare i pesi alla tabella?
grazie cionci...
questo è il grafo da te segnalato:
http://it.wikipedia.org/wiki/Algoritmo_di_Dijkstra
questo è il file testo di caricamento dei vertici:
NODI 07 LINK 16 PARTENZA 01 ARRIVO 07
1 2 2.00
1 3 8.00
2 5 6.00
2 4 2.00
2 1 2.00
3 1 8.00
3 4 2.00
3 6 3.00
4 2 2.00
4 3 2.00
4 5 9.00
5 2 6.00
5 7 5.00
6 3 3.00
6 4 9.00
6 7 1.00
questo è il risultato:
1 --> 2 --> 4 --> 3 --> 6 --> 7
Time 0.0163 ms
vBulletin® v3.6.4, Copyright ©2000-2026, Jelsoft Enterprises Ltd.