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);
}