Gli esercizi
Testi e soluzioni di alcuni esercizi
Ciclo hamiltoniano
/*
** hamiltoniano.c
**
** Leggere in input un grafo orientato G=(V,E) ed una sequenza
** S di vertici di G. Verificare se S e' un ciclo hamiltoniano,
** ossia un ciclo semplice in G che consente di raggiungere
** tutti i vertici di G. Il grafo G deve essere rappresentato
** utilizzando la struttura dati delle liste di adiacenza, la
** sequenza S deve essere rappresentata mediante una lista.
**
** Marco Liverani (liverani@mat.uniroma3.it) - Settembre 2001
*/
#include <stdlib.h>
#include <stdio.h>
#define MAX 50
struct nodo {
int info;
struct nodo *next;
};
struct nodo *leggi_lista(void) {
struct nodo *p, *primo, *ultimo;
int a, i, n;
primo = NULL;
ultimo = NULL;
printf("Numero di elementi: ");
scanf("%d", &n);
for (i=0; i<n; i++) {
scanf("%d", &a);
p = malloc(sizeof(struct nodo));
p->info = a;
p->next = NULL;
if (!primo)
primo = p;
if (ultimo)
ultimo->next = p;
ultimo = p;
}
return(primo);
}
int leggi_grafo(struct nodo *l[]) {
int i, n;
printf("Numero di vertici del grafo: ");
scanf("%d", &n);
for (i=0; i<n; i++) {
printf("Lista di adiacenza del vertice %d\n", i);
l[i] = leggi_lista();
}
return(n);
}
int adiacente(int u, int v, struct nodo *l[]) {
struct nodo *p;
p = l[u];
while (p!=NULL && p->info != v)
p = p->next;
if (p == NULL)
return(0);
else
return(1);
}
int hamiltoniano(struct nodo *primo, struct nodo *l[], int n) {
int visitato[MAX], i, flag;
struct nodo *p;
for (i=0; i<n; i++)
visitato[i] = 0;
p = primo;
visitato[p->info] = 1;
while (p->next != NULL && !visitato[p->next->info] && adiacente(p->info, p->next->info, l)) {
visitato[p->next->info] = 1;
p = p->next;
}
flag = 1;
for (i=0; i<n && flag==1; i++)
flag = visitato[i];
return(flag);
}
int main(void) {
struct nodo *lista[MAX], *primo;
int n;
n = leggi_grafo(lista);
primo = leggi_lista();
if (hamiltoniano(primo, lista, n))
printf("La sequenza di vertici e' un ciclo hamiltoniano in G.\n");
else
printf("La sequenza di vertici non e' un ciclo hamiltoniano.\n");
return(0);
}