Gli esercizi
Testi e soluzioni di alcuni esercizi
Verifica di un cammino su un grafo
Leggere in input un grafo G=(V,E) con n vertici (V = {0, 1, 2, 3, ..., n-1}) e rappresentarlo mediante liste di adiacenza; generare una sequenza di k numeri casuali minori di n e memorizzarla nel vettore S. Stampare le liste di adiacenza del grafo e la sequenza S. Verificare che gli elementi di S rappresentino un cammino su G (cioè (Si,Si+1) ∈ E(G) per i=0, 1, ..., n-2).
/* ** cammino.c ** ** Memorizza il grafo G con liste di adiacenza, genera una sequenza S ** di numeri casuali e verifica che S sia un cammino su G. ** ** Marco Liverani (liverani@mat.uniroma3.it) - Novembre 2012 */ #include <stdlib.h> #include <stdio.h> #include <time.h> #define MAX 100 struct nodo { int info; struct nodo *next; }; /* * Acquisisce in input una sequenza di n interi e la memorizza * in una lista; restituisce l'indirizzo del primo elemento della lista. */ struct nodo *leggiLista(void) { struct nodo *p, *primo = NULL; int i, n; printf("Numero di elementi: "); scanf("%d", &n); printf("Elementi della lista: "); for (i=0; i<n; i++) { p = malloc(sizeof(struct nodo)); scanf("%d", &p->info); p->next = primo; primo = p; } return(primo); } /* * Acquisice in input le n liste di adiacenza dei vertici del grafo G. */ int leggiGrafo(struct nodo *V[]) { int i, n; printf("\nNumero di vertici del grafo: "); scanf("%d", &n); for (i=0; i<n; i++) { printf("\nLista di adiacenza del vertice %d:\n", i); V[i] = leggiLista(); } return(n); } /* * Stampa gli elementi di una lista. */ void stampaLista(struct nodo *p) { while (p != NULL) { printf("%d --> ", p->info); p = p->next; } printf("NULL\n"); return; } /* * Stampa le liste di adiacenza dei vertici del grafo G. */ void stampaGrafo(struct nodo *V[], int n) { int i; printf("Liste di adiacenza del grafo:\n"); for (i=0; i<n; i++) { printf("%2d: ", i); stampaLista(V[i]); } return; } /* * Genera un array di numeri casuali minori di una soglia. */ int generaVettore(int S[], int soglia) { int i, n; printf("\nNumero di elementi della sequenza casuale: "); scanf("%d", &n); srand((unsigned)time(NULL)); for (i=0; i<n; i++) S[i] = rand() % soglia; return(n); } /* * Stampa gli elementi di un vettore di numeri interi. */ void stampaVettore(int S[], int n) { int i; printf("\n"); for (i=0; i<n; i++) printf("%d ", S[i]); printf("\n"); return; } /* * Restituisce "vero" (1) se x e y sono adiacenti in G, restituisce * "falso" (0) altrimenti. */ int adiacenti(struct nodo *V[], int x, int y) { int risp; struct nodo *p; p = V[x]; while (p != NULL && p->info != y) p = p->next; if (p != NULL) risp = 1; else risp = 0; return(risp); } /* * Verifica se gli elementi di S rappresentano un cammino sul grafo G. * Restituisce 1 (vero) se S e' un cammino, 0 (falso) altrimenti. */ int verificaCammino(int S[], int k, struct nodo *V[], int n) { int i, risp=1; for (i=0; i<k-1 && risp==1; i++) if (!adiacenti(V, S[i], S[i+1])) risp = 0; return(risp); } /* * Funzione principale. */ int main(void) { struct nodo *V[MAX]; int n, k, S[MAX]; n = leggiGrafo(V); k = generaVettore(S, n); stampaGrafo(V, n); stampaVettore(S, k); if (verificaCammino(S, k, V, n)) printf("La sequenza e' un cammino su G\n"); else printf("La sequenza NON e' un cammino su G\n"); return(0); }