[C] liste di adiacenza

[misterx]

struct node { /* nodo di lista di adiacenza */
int v;
struct node *next;
};
struct graph { /* struttura associata a ogni grafo */
int V; /* numero nodi */
int E; /* numero archi */
struct node **A; /* array di liste di adiacenza */
};


mi servirebbe una conferma su ciò che ho postato e cioè: supponendo di avere un grafo fatto da 3 nodi e tre archi, allocherei una ed una sola struttura di tipo graph con V=3 ed E=3, e l'array **A conterrebbe tre puntatori a 3 strutture di tipo node, ma è così ?

grazie

[misterx]

domanda troppo banale ? :)

mi rispondo da solo, è così

[misterx]

implementando un grafo attraverso un array ed un certo numero di liste di adiacenza, come le si percorre ?

[misterx]

speriamo di non continuare a parlare da solo!

Una lista di adiacenza è una serie di strutture concatenate attraverso puntatori e racchiusa tra due NULL che ne definiscono i limiti ?

[Furla]

perché dici "racchiusa tra due null"? cosa intendi per "come le si percorre"? non si capisce cosa non capisci :p

[jobzino]

per percorrerlo una volta ke sai di quale vertice ti interessa la lista di adiacenza fai:
edge *e usi un puntatore di appoggio
e=G->adj[VERTICE]

e ti scorri la lista puntata da "e" che sarebbe la testa della lista di adiacenza del vertice (come scorreresti una semplice lista).. se non usi questo puntatore di appoggio perdi la testa della lista di adiacenza del vertice..
Spero di essere stato chiaro
Questo potrebbe aiutarti qui (http://people.na.infn.it/~murano/LASD-learning/lezione-15.pdf) forse ti chiarisci meglio le idee...

[misterx]

perché dici "racchiusa tra due null"? cosa intendi per "come le si percorre"? non si capisce cosa non capisci :p

niente, è una cavolata priva di senso!
Ho visto poi che si implementa con un array ed un certo numero di liste di adiacenza.
Ora sto vedendo come si implementa la visita in profondità di un grafo e poi in ampiezza, per giungere infine ad implementare Dijkstra.

[misterx]

per percorrerlo una volta ke sai di quale vertice ti interessa la lista di adiacenza fai:
edge *e usi un puntatore di appoggio
e=G->adj[VERTICE]

e ti scorri la lista puntata da "e" che sarebbe la testa della lista di adiacenza del vertice (come scorreresti una semplice lista).. se non usi questo puntatore di appoggio perdi la testa della lista di adiacenza del vertice..
Spero di essere stato chiaro
Questo potrebbe aiutarti qui (http://people.na.infn.it/~murano/LASD-learning/lezione-15.pdf) forse ti chiarisci meglio le idee...


chiarissimo!