[algoritmi] liste di adiacenza sequenziali e grafi (era: grafi aiuto)

[graziano mesina]

salve a tutti,
vorrei sapere se il metodo delle "liste di adiacenza sequenziali" utilizzate per rappresentare i grafi è applicabile sia ai grafi non orientati ke orientati.

se si quali sono le regole per i grafi orientati??
(x esempio: x i grafi non orientati la posizione n contiene il valore n+[2L]+1, dove n è il numero dei nodi e L è il numero dei lati.
Inoltre dalla posizione [i] a [i+1]-1 sono memorizzati tutti i vertici adiacenti al vertice i)...

[graziano mesina]

uhmmmm.... nessuno è in grado di "illuminarmi"??

[kommsoft]

anche io avrei la stessa domanda

ho anche un esercizio svolto ma non riesco a capire come realizzare il vett

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

[Bado80]

direi che hai un grafo con 6 nodi (da A a F).
i primi 6 elementi del vettore rappresentano l'inizio di ogni sequenza:
0->A
1->B
.
.
5->F

Parti da a[0] elemento associato alla A
a[0]=7 per cui vado su a[7]=1 cioè B, poi a[8]=3 cioè D, poi a[9]=0 quindi NULL (A è la partenza della sequenza, quindi si chiude la prima sequenza)

quindi la prima sequenza è: A->B->D->NULL

Poi passo su a[1] elemento partenza per B
a[1]=9, vado su a[9]=0 cioè A, a[10]=2 cioè C, a[11]=1 quindi NULL (si chiude la sequenza)

quindi la seconda sequenza è: B->A->C->NULL

e vai avanti così.

In pratica se hai un grafo ad N nodi i primi N elementi dell'array sono i punti di partenza per la sequenza associata ad ogni nodo.

Non capisco bene l'uso del valore 19 per cui ci sono ancora particolari da capire ma grosso modo direi che è così..

[kommsoft]

CAPITO!!! THNXXXXXXXXXXX MILLE DDDD