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