Gli esercizi

Testi e soluzioni di alcuni esercizi

Verifica di un cammino su un grafo

Leggere in input un grafo G=(V,E) con n vertici (V = {0, 1, 2, 3, ..., n-1}) e rappresentarlo mediante liste di adiacenza; generare una sequenza di k numeri casuali minori di n e memorizzarla nel vettore S. Stampare le liste di adiacenza del grafo e la sequenza S. Verificare che gli elementi di S rappresentino un cammino su G (cioè (S_i,S_i+1) ∈ E(G) per i=0, 1, ..., n-2).

/*
**	cammino.c
**
**	Memorizza il grafo G con liste di adiacenza, genera una sequenza S
**	di numeri casuali e verifica che S sia un cammino su G.
**
**	Marco Liverani (liverani@mat.uniroma3.it) - Novembre 2012
*/

#include <stdlib.h>
#include <stdio.h>
#include <time.h>
#define MAX 100

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


/*
 *	Acquisisce in input una sequenza di n interi e la memorizza
 *	in una lista; restituisce l'indirizzo del primo elemento della lista.
 */

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

/*
 *	Acquisice in input le n liste di adiacenza dei vertici del grafo G.
 */

int leggiGrafo(struct nodo *V[]) {
  int i, n;
  printf("\nNumero di vertici del grafo: ");
  scanf("%d", &n);
  for (i=0; i<n; i++) {
    printf("\nLista di adiacenza del vertice %d:\n", i);
    V[i] = leggiLista();
  }
  return(n);
}

/*
 *	Stampa gli elementi di una lista.
 */

void stampaLista(struct nodo *p) {
  while (p != NULL) {
    printf("%d --> ", p->info);
    p = p->next;
  }
  printf("NULL\n");
  return;
}

/*
 *	Stampa le liste di adiacenza dei vertici del grafo G.
 */

void stampaGrafo(struct nodo *V[], int n) {
  int i;
  printf("Liste di adiacenza del grafo:\n");
  for (i=0; i<n; i++) {
    printf("%2d: ", i);
    stampaLista(V[i]);
  }
  return;
}

/*
 *	Genera un array di numeri casuali minori di una soglia.
 */

int generaVettore(int S[], int soglia) {
  int i, n;
  printf("\nNumero di elementi della sequenza casuale: ");
  scanf("%d", &n);
  srand((unsigned)time(NULL));
  for (i=0; i<n; i++)
    S[i] = rand() % soglia;
  return(n);
}

/*
 *	Stampa gli elementi di un vettore di numeri interi.
 */

void stampaVettore(int S[], int n) {
  int i;
  printf("\n");
  for (i=0; i<n; i++)
    printf("%d ", S[i]);
  printf("\n");
  return;
}

/*
 *	Restituisce "vero" (1) se x e y sono adiacenti in G, restituisce
 *	"falso" (0) altrimenti.
 */

int adiacenti(struct nodo *V[], int x, int y) {
  int risp;
  struct nodo *p;
  p = V[x];
  while (p != NULL && p->info != y)
    p = p->next;
  if (p != NULL) 
    risp = 1;
  else
    risp = 0;
  return(risp);
}

/*
 *	Verifica se gli elementi di S rappresentano un cammino sul grafo G.
 *	Restituisce 1 (vero) se S e' un cammino, 0 (falso) altrimenti.
 */

int verificaCammino(int S[], int k, struct nodo *V[], int n) {
  int i, risp=1;
  for (i=0; i<k-1 && risp==1; i++)
    if (!adiacenti(V, S[i], S[i+1]))
      risp = 0;
  return(risp);
}

/*
 *	Funzione principale.
 */

int main(void) {
  struct nodo *V[MAX];
  int n, k, S[MAX];
  n = leggiGrafo(V);
  k = generaVettore(S, n);
  stampaGrafo(V, n);
  stampaVettore(S, k);
  if (verificaCammino(S, k, V, n))
    printf("La sequenza e' un cammino su G\n");
  else
    printf("La sequenza NON e' un cammino su G\n");
  return(0);
}