Questo sito utilizza cookies, anche di terze parti, per mostrare pubblicità e servizi in linea con il tuo account. Leggi l'informativa sui cookies.
Username: Password: oppure
C/C++ - [Strutture Dati] Grafi rappresentati attraverso liste di adiacenza (sequenziali) e multiliste?
Forum - C/C++ - [Strutture Dati] Grafi rappresentati attraverso liste di adiacenza (sequenziali) e multiliste?

Avatar
kommsoft (Normal User)
Newbie


Messaggi: 2
Iscritto: 17/07/2009

Segnala al moderatore
Postato alle 12:55
Venerdì, 17/07/2009
Salve sono nuovo!! Un saluto a tutti e complimenti x il blog!!!  nel corso dello studio mi sono imbattuto in delle rappresentazioni di grafi attraverso strutture dati un po particolari:

Riesco a comprendere e rappresentare senza difficolta attraverso matrici di adiacenza e liste adiacenza concatenate i grafi. Ma non riesco a comprendere le regole per generare le rappresentazioni attraverso liste di adiacenza sequenziali e Multigrafi pur avendo la soluzione agli esercizi :

Esempio: Un grafo che ha come liste di adiacenza concatenate
a-> b->d->->(NULL)
b->a->c->(NULL)
c->d->b->e->(NULL)
d->a->c->e->(NULL)
e->d->c->(NULL)
f->(NULL)

le liste di adiacenza sequenziali sono rappresentate in un vettore di n+2l+1=19 nodi (dove n=nodi; l=lati )
a[0]=7
a[1]=9
a[2]=11
a[3]=14
a[4]=17
a[5]=19
a[6]=19
a[7]=1
a[8]=3
a[9]=0
a[10]=2
a[11]=1
a[12]=3
a[13]=4
a[14]=0
a[15]=2
a[16]=4
a[17]=2
a[18]=3

Come faccio a calcolarmi questo vettore?
/////////////
Stessa cosa per i multigrafi con lo stesso esempio:
Rappresentati arraverso la struttura [marcato,vertice1,vertice2,percorso1,per…
dove N(i) per i che va da 1 a l(numero lati) rappresenta il collegamento tra 2 nodi.


vertice0=N1->N3
vertice1=N1->N2
vertice2=N2->N4->N6
vertice3=N3->N4->N5
vertice4=N5->N6
vertice5=NULL


le multiliste sono
#0 1 n3 n2
#1 2 NULL n4
#0 3 NULL n4
#2 3 n6 n5
#3 4 NULL n6
#2 4 NULL NULL


Grazie x l'attenzione..
spero possiate darmi una mano :))

PM Quote
Avatar
TheKaneB (Member)
Guru^2


Messaggi: 1787
Iscritto: 26/06/2009

Segnala al moderatore
Postato alle 16:08
Sabato, 18/07/2009
Ciao,

ho dato un'occhiata al tuo esercizio. L'algoritmo è molto semplice ma in questo momento vado di fretta e non ho il tempo di scriverlo.

Resta comunque nei paraggi, se domani trovo un po' di tempo ti faccio vedere come ottenere il vettore con un algoritmo iterativo piccolissimo, saranno a occhio e croce meno di 10 linee di codice.

Ciao, a presto ;-)


Software Failure: Guru Meditation
Forum su Informatica, Elettronica, Robotica e Tecnologia: http://www.nonsoloamiga.com
PM Quote
Avatar
kommsoft (Normal User)
Newbie


Messaggi: 2
Iscritto: 17/07/2009

Segnala al moderatore
Postato alle 11:38
Martedì, 21/07/2009
Risolto :)) grazie lo stesso !!!

PM Quote
Avatar
TheKaneB (Member)
Guru^2


Messaggi: 1787
Iscritto: 26/06/2009

Segnala al moderatore
Postato alle 16:26
Martedì, 21/07/2009
uh, ok :-)

scusa il ritardo ma in questo periodo ho poco tempo libero... eheh ^_^


Software Failure: Guru Meditation
Forum su Informatica, Elettronica, Robotica e Tecnologia: http://www.nonsoloamiga.com
PM Quote
Avatar
dani_adp (Normal User)
Newbie


Messaggi: 1
Iscritto: 30/08/2009

Segnala al moderatore
Postato alle 9:11
Domenica, 30/08/2009
Testo quotato

Postato originariamente da kommsoft:

Risolto :)) grazie lo stesso !!!  



io invece non riesco proprio a capire come riempire il vettore.Qualcuno mi può dare una mano??:-| Grazie!

PM Quote