Gli esercizi
Testi e soluzioni di alcuni esercizi
Costruzione del grafo complementare
Dato un grafo G(V,E), con |V|=n, espresso mediante liste di adiacenza, generare le liste di adiacenza del grafo G'(V,E') complementare a G, dove E' = {(u,v) tale che (u,v) ∉ E}.
/* ** complementare.c ** ** Dato un grafo G(V,E), con |V|=n, espresso mediante liste di ** adiacenza, generare le liste di adiacenza del grafo G'(V,E') ** complementare a G (E' = {(u,v) tale che (u,v) non appartiene ** ad E). ** ** Algoritmo: ** 1. calcolo le liste di adiacenza del grafo completo G"; ** 2. elimino dalle liste di adiacenza di G" tutti gli spigoli ** presenti in G ed ottengo G'. ** ** Marco Liverani (liverani@mat.uniroma3.it) - Gennaio 1999 */ #include <stdlib.h> #include <stdio.h> #define MAX 50 struct nodo { int info; struct nodo *next; }; /* ** leggi_lista ** ** legge in input una sequenza di numeri interi fino a quando ** l'utente non digita "-1". I numeri letti vengono man mano ** memorizzati in una lista. La funzione restituisce un puntatore ** al primo elemento della lista (l'indirizzo di memoria del ** primo elemento della lista). */ struct nodo *leggi_lista(void) { int a; struct nodo *p, *primo; primo = NULL; scanf("%d", &a); while (a != -1) { p = malloc(sizeof(struct nodo)); p->info = a; p->next = primo; primo = p; scanf("%d", &a); } return(primo); } /* ** leggi_grafo ** ** per ogni vertice del grafo ne legge la lista di adiacenza. ** Restituisce il numero di vertici. */ int leggi_grafo(struct nodo **l) { int i, n; printf("Numero dei vertici: "); scanf("%d", &n); for (i=0; i<n; i++) { printf("%d: ", i); *(l+i) = leggi_lista(); } return(n); } /* ** stampa_lista ** ** visualizza in output una lista di adiacenza; si aspetta come ** parametro l'indirizzo di memoria (il puntatore) del primo ** elemento della lista. */ void stampa_lista(struct nodo *primo) { while (primo != NULL) { printf("%d -> ", primo->info); primo = primo->next; } printf("NULL\n"); return; } /* ** grafo_completo ** ** costruisce le liste di adiacenza di un grafo completo di n ** vertici (|V| = n). Aspetta come parametri il numero n di ** vertici ed il puntatore al primo elemento dell'array dei ** puntatori ai primi elementi delle liste di adiacenza. */ void grafo_completo(int n, struct nodo **lista) { int i, j; struct nodo *p; for (i=0; i<n; i++) { *(lista+i) = NULL; for (j=0; j<n; j++) { if (i != j) { p = malloc(sizeof(struct nodo)); p->info = j; p->next = *(lista+i); *(lista+i) = p; } } } return; } /* ** riduzione ** ** costruisce il grafo complementare G' di G, riducendo il ** grafo completo G", eliminando gli spigoli che sono ** in G. Accetta come parametri il puntatore agli array ** con le liste di adiacenza di G e di G" ed il numero ** n di vertici. */ void riduzione(int n, struct nodo **lista1, struct nodo **lista2) { int i; struct nodo *p1, *p2, *prec_p2; for (i=0; i<n; i++) { /* per ogni elemento di G... */ p1 = *(lista1+i); while (p1 != NULL) { /* scorro la lista di adiacenza dell'elemento fissato */ prec_p2 = NULL; p2 = *(lista2+i); /* ** salto tutti gli elementi di lista2 che sono diversi ** dall'elemento fissato di lista1. */ while (p2->info != p1->info) { prec_p2 = p2; p2 = p2->next; } /* ** quando esco dal ciclo p2 punta sicuramente ad un elemento ** uguale a cio' a cui punta p1. Quindi posso eliminarlo ** dalla lista "lista2". */ if (prec_p2 == NULL) { *(lista2+i) = p2->next; } else { prec_p2->next = p2->next; free(p2); p2 = prec_p2->next; } p1 = p1->next; } } return; } /* ** main ** ** la funzione principale richiama tutte le altre. */ int main(void) { struct nodo *l1[MAX], *l2[MAX]; int i, n; /* ** il grafo G viene fornito in input dall'utente */ n = leggi_grafo(&l1[0]); /* ** il grafo completo G" viene costruito automaticamente ** dalla funzione grafo_completo. */ grafo_completo(n, &l2[0]); /* ** costruisco il grafo complementare G' di G riducendo G" */ riduzione(n, &l1[0], &l2[0]); /* ** stampo le liste di adiacenza del nuovo grafo */ for (i=0; i<n; i++) { printf("%d: ", i); stampa_lista(l2[i]); } return(0); }