Gli esercizi

Testi e soluzioni di alcuni esercizi

Grado entrante e grado uscente

/*
**  grado.c
**
**  Letto in input un grafo orientato, rappresentarlo
**  mediante liste di adiacenza.
**  Stampare in output il grado entrante ed uscente di
**  ogni vertice del grafo.
**
**  Marco Liverani (liverani@mat.uniroma3.it) - Maggio 2001
**
*/

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

/*
 *  definizione della costante che indica la massima dimensione
 *  del grafo (|V|<MAX).
 */

#define MAX 100

/*
 *  struttura per la rappresentazione dei nodi della lista
 */

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

/*
 *  Legge in input una sequenza di n interi e li memorizza su
 *  una lista. Restituisce il puntatore al primo elemento della lista.
 */

struct nodo *leggi_lista(void) {
  struct nodo *p, *primo;
  int x, n, i;

  printf("Numero di elementi nella lista: ");
  scanf("%d", &n);
  primo = NULL;
  for (i=0; i<n; i++) {
    scanf("%d", &x);
    p = malloc(sizeof(struct nodo));
    p->info = x;
    p->next = primo;
    primo = p;
  }
  return(primo);
}

/*
 *  Legge in input le n liste di adiacenza (una per ogni
 *  vertice del grafo G). Restituisce il numero di vertici
 *  di cui e' costituito il grafo e l'array di puntatori
 *  ai primi elementi di ogni lista di adiacenza.
 */

int leggi_grafo(struct nodo *lista[]) {
  int i, n;
  printf("Numero di vertici: ");
  scanf("%d", &n);
  for (i=0; i<n; i++) {
    printf("Lista di adiacenza del vertice %d.\n", i);
    lista[i] = leggi_lista();
  }
  return(n);
}

/*
 *  Calcola il grado entrante ed uscente di ogni vertice i del grafo.
 *  Memorizza in in[i] e in out[i] rispettivamente il grado entrante
 *  ed il grado uscente del vertice i.
 */

void calcola(int n, struct nodo *l[], int in[], int out[]) {
  int i;
  struct nodo *p;

  for (i=0; i<n; i++) {
    in[i] = 0;
    out[i] = 0;
  }
  for (i=0; i<n; i++) {
    p = l[i];
    while (p != NULL) {
      out[i]++;
      in[p->info]++;
      p = p->next;
    }
  }
  return;
}

/*
 *  Funzione principale.
 */

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

  n = leggi_grafo(lista);
  calcola(n, lista, grado_in, grado_out);
  for (i=0; i<n; i++) {
    printf("vertice %d: grado entrante = %d, grado uscente = %d\n", i, grado_in[i], grado_out[i]);
  }
  return(0);
}