Gli esercizi

Testi e soluzioni di alcuni esercizi

Trasformazione di una matrice di adiacenza di un grafo in liste di adiacenza

Data in input la matrice di adiacenza di un grafo G(V,E), costruire e stampare le liste di adiacenza dello stesso grafo.

/*
**  matrice_lista.c
**
**  Legge in input un grafo G(V,E) come matrice di adiacenza. Costruisce
**  le liste di adiacenza relative allo stesso grafo e le stampa.
**
**  Marco Liverani (liverani@mat.uniroma3.it) - Gennaio 1999
*/

#include <stdlib.h>
#include <stdio.h>

#define MAX 50

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


/*
**  stampa_matrice
**
**  stampa la matrice; accetta come parametri il puntatore
**  al primo elemento, il numero di righe ed il numero di
**  colonne.
*/

void stampa_matrice(int *m, int righe, int colonne) {
  int i, j;

  for (i=0; i<righe; i++) {
    for (j=0; j<colonne; j++) {
      printf("%2d ", *(m+i*MAX+j));
    }
    printf("\n");
  }
  return;
}


/*
**  leggi_grafo
**
**  legge il grafo e costruisce la matrice di adiacenza. Accetta in
**  input l'indirizzo di memoria (il puntatore) del primo elemento
**  della matrice. Restituisce il numero di vertici.
*/

int leggi_grafo(int *m) {
  int i, j, n;

  printf("Numero dei vertici: ");
  scanf("%d", &n);

  for (i=0; i<n; i++) {

    for (j=0; j<n; j++) {
      *(m+i*MAX+j) = 0;
    }

    printf("%d: ", i);
    while (j != -1) {
      *(m+i*MAX+j) = 1;
      scanf("%d", &j);
    }
  }

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


/*
**  costruisci_liste
**
**  Accetta come parametro il puntatore al primo elemento della
**  matrice di adiacenza e costruisce le liste di adiacenza relative.
*/

void costruisci_liste(int *m, int n, struct nodo **l) {
  int i, j;
  struct nodo *p, *primo;

  for (i=0; i<n; i++) {
    *(l+i) = NULL;
    for (j=0; j<n; j++) {
      if (*(m+i*MAX+j) == 1) {
        p = malloc(sizeof(struct nodo));
        p->info = j;
        p->next = *(l+i);
        *(l+i) = p;
      }
    }
  }
  return;
}

/*
**  main
**
**  la funzione principale richiama tutte le altre.
*/

int main(void) {
  struct nodo *lista[MAX];
  int matrice[MAX][MAX];
  int i, n;

  n = leggi_grafo(&matrice[0][0]);

  stampa_matrice(&matrice[0][0], n, n);

  costruisci_liste(&matrice[0][0], n, &lista[0]);

  for (i=0; i<n; i++) {
    printf("%d: ", i);
    stampa_lista(lista[i]);
  }

  return(0);
}