Gli esercizi

Testi e soluzioni di alcuni esercizi

Trasformazione delle liste di adiacenza di un grafo nella matrice di adiacenza equivalente

Date le liste di adiacenza di un grafo G=(V,E), costruisce e stampa la matrice di adiacenza dello stesso grafo.

/*
**  lista_matrice.c
**
**  Legge in input un grafo G(V,E) memorizzando le liste di adiacenza.
**  Quindi costruisce la matrice di adiacenza dello stesso grafo e la
**  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;
};

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


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


/*
**  costruisci_matrice
**
**  Accetta come parametro il puntatore al primo elemento della
**  matrice di adiacenza da costruire, il numero di vertici del
**  grafo ed il puntatore al primo elemento dell'array dei
**  puntatori alle liste di adiacenza e costruisce la matrice.
*/

void costruisci_matrice(int *m, int n, struct nodo **l) {
  int i, j;
  struct nodo *p, *primo;
  for (i=0; i<n; i++) {
    for (j=0; j<n; j++) {
      *(m+i*MAX+j) = 0;
    }
    p = *(l+i);
    while (p != NULL) {
      *(m+i*MAX+ p->info) = 1;
      p = p->next;
    }
  }
  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(&lista[0]);
  for (i=0; i<n; i++) {
    printf("%d: ", i);
    stampa_lista(lista[i]);
  }
  costruisci_matrice(&matrice[0][0], n, &lista[0]);
  stampa_matrice(&matrice[0][0], n, n);
  return(0);
}