[C] Implementare grafi attraverso le strutture

[rachid]

come se implementano i grafi in c attraverso le strutture?
è molto importante per me saperlo visto che devo fare un progetto con essi per es [commesso viaggiatore]
vi ringrazio anticipatamente.

[Mr.Bloom]

Dunque se la memoria non mi fa difetto gli approcci sono fondamentalmente due:
Matrice di adiacenza e array di liste.

sia un grafo G composto da V vertici ed E archi:

Matrice di adiac:
allochi una matrice di VxV elementi e sia sulle righe che sulle colonne l' i-esimo
elemento rappresenta l' i-esimo vertice, la casella i,j della matrice vale uno
se esiste un'arco tra il nodo i e il nodo j, 0 altrimenti.

array di liste:
allochi un array di V puntatori a struct nodo per fare una lista, fatta tipo:
struct nodo { int vertex, struct nodo *next}
l'i-esima cella dell'array rappresenta l'i-esimo vertice e la lista che si diparte da essa
contiene tutti gli elementi j tale che esiste un arco fra i e j.

[rachid]

non ha un esempio?

[Mr.Bloom]

esempio di cosa?

[rachid]

1)come costruire/aggiungere un nodo?
2)come eliminare un nodo?
3)cm stampare il grafo?
se no un sito dove le spiega queste cose?
grazie per le tue future risposte.

[Mr.Bloom]

Beh non posso scrivere io il codice per te, penso di essere stato esaustivo
nella mia risposta su come rappresentare un grafo in C,poi come farlo
realmente te lo ricavi dallo studio di un qualsiasi manuale di C.

......vabbè giusto perchè è natale....ti scrivo a braccio un abbozzo di codice
per inserire un arco fra due nodi. il grafo ha 10 nodi identificati dai numeri
da 0 a 9.

struct nodo {
    int id;
    struct nodo *next
};

struct nodo *grafo[10];//da inizializzare tutto a NULL

void inserisci_arco(struct nodo *origine, int desitinazione){
   struct nodo *temp;
   temp = origine;
   
   origine = (struct nodo*)malloc(sizeof(struct nodo));
   if (origine == NULL){
       printf("per fortuna non ho dimenticato di controllare il valore di ritorno della malloc\n");
       exit(EXIT_FAILURE);
   }

  origine->id = destinazone;
  origine->next = temp;
  return;
}


   /* per inserire un arco da 5 a 3*/
   /* fai inserisci_arco(&grafo[5],3) */

quindi alla fine di tutti gli inserimenti per fare un esempio grafo[4] sara un
puntatore ad una lista contenente tutti gli archi che partono dal nodo 4.
per cancellare un arco fra i e j fai la free sull'elemento della lista grafo[i] che contiene id= j.

[rachid]

Grazie mille.....