Grafi

La parte di programma sui grafi è trattata in modo esauriente sul libro. Queste pagine contengono soltanto il programma di generazione e salvataggio su file di un grafo random, e la lettura di un grafo da file.

1. definizione di tipo e operazioni fondamentali per grafi rappresentato come matrice di adiacenza: adiac.c
   
2. definizione di tipo e operazioni fondamentali per grafi rappresentato come liste di successori: success.c

3. programma di generazione di grafi random: randgraf.c (in questo programma la costante NUMNODI vale 12). Il file contiene la matrice di adiacenza del grafo.

4. lettura di un grafo da un file che contiene la sua matrice di adiacenza:

   TipoGrafo LeggiGrafoFileMatrice(char *nomefile) {
     TipoGrafo g;
     FILE *fd;
     int i, j;
     int x, res;
   
     g=InitGrafo();
   
     fd=fopen(nomefile, "r");
     if(fd==NULL) {
       perror("Errore in apertura del file grafo");
       exit(1);
     }
   
     for(i=0; i<=NUMNODI-1; i++)
       for(j=0; j<=NUMNODI-1; j++) {
         res=fscanf(fd, "%d", &x);
         if(res!=1)
           return g;
   
         if(x)
           g=InserArco(g, i, j);
       }
   
     return g;
   }
   
   

   Notare che questa funzione, dal momento che usa solo le operazioni fondamentali sui grafi, è corretta sia se TipoGrafo è la matrice di adicenza, sia nel caso in cui TipoGrafo è definito come vettore delle liste di successori. Quindi, anche se il file contiene la matrice di adiacenza del grafo, il risulato della funzione è comunque il grafo rappresentato in base alla definizione data dal tipo TipoGrafo, che può essere sia matrice di adiacenza che liste di successori.

5. Esercizio: scrivere una funzione che verifica se una lista è un cammino di un grafo. Soluzione:

   bool VerificaCammino(TipoGrafo g, TipoLista l) {
     if(l==NULL)
       return TRUE;
   
     if(l->val>NUMNODI-1 || l->val<0)
       return FALSE;
   
     if(l->next==NULL)
       return TRUE;
   
     while(l->next!=NULL) {
       if(!TestEsisteArco(g, l->val, l->next->val))
         return FALSE;
   
       l=l->next;
     }
   
     return TRUE;
   }