mikael_c
13-09-2013, 17:08
Devo modificare il codice sottostante in modo che il vettore permutazione nella generazione di tutte le possibili possibilità sceglie solo i vertici adiacenti.Il grafo deve essere rappresentato con lista di adiacenza.
Codice della permutazione
/*
VARIABILI GLOBALI:
n
nChr = numero di permutazioni alcolate (inizialmente 0)
Chr = permutazione
Chr1 = permutazione inversa (Chr1[i] = n equivale ad elemento di permutazione non definito
(se Chr[i]=j, allora Chr1[i]=j)
Succ = risposta della procedura genTPerm (inizialmente 1)
*/
int Chr[100]; /* vettore soluzione (permutazione) */
int Chr1[100]; /* soluzione inversa */
int nChr=0; /* numero soluzioni costruite dalla procedura esaustiva */
int Succ=1; /* flag che indica il successo della procedura esaustiva */
int n=3; /* numero vertici digrafi */
/* procedura di inizializzazione dei vettori soluzione (Chr[] e Chr1[]) */
void initChr()
{
int i=0;
for(i=0;i<n;i++)
{
Chr[i]=n;
Chr1[i]=n;
}
}
/* procedura di stampa di Chr[] */
void stampaVett()
{
int i=0;
for(i=0;i<n;i++)
printf ("%d ",Chr[i]);
printf("\n");
}
/* procedura esaustiva di calcolo soluzioni */
/* metto 0 nella prima posizione e generola permutazione su 1 2,
poi metto 1 nella prima posizione e genero la permutazione su 0 2,
ed infine metto 2 nella prima posizione e genero la permutazione su 0 1 , */
void genTPerm(int k)
{
int i=0;
if(k>(n-1))
{
stampaVett();
/* verifica se la soluzione trovata è un ciclo: se si succ=1 e termina genTPerm */
nChr++;
if(nChr>n)
{
Succ=0;
return ;
}
}
else
for(i=0;i<n;i++)
{if(Chr1[i]==n)
{Chr[k]=i;
Chr1[i]=k;
genTPerm(k+1);
Chr1[i]=n;
Chr[k]=n;
}
}
}
/* programma principale */
int main(void)
{
int i=0, k=0;
/* inizializza variabili, vettori e strutture dati */
nChr = 0;
initChr(); /* procedura che inizializza Chr e Chr1 */
genTPerm(0); /* procedura esaustiva per il calcolo di soluzioni */
}
Questo è il codice di un grafo con lista di adiacenza viene eseguito però non so se va bene:
#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);
}
Codice della permutazione
/*
VARIABILI GLOBALI:
n
nChr = numero di permutazioni alcolate (inizialmente 0)
Chr = permutazione
Chr1 = permutazione inversa (Chr1[i] = n equivale ad elemento di permutazione non definito
(se Chr[i]=j, allora Chr1[i]=j)
Succ = risposta della procedura genTPerm (inizialmente 1)
*/
int Chr[100]; /* vettore soluzione (permutazione) */
int Chr1[100]; /* soluzione inversa */
int nChr=0; /* numero soluzioni costruite dalla procedura esaustiva */
int Succ=1; /* flag che indica il successo della procedura esaustiva */
int n=3; /* numero vertici digrafi */
/* procedura di inizializzazione dei vettori soluzione (Chr[] e Chr1[]) */
void initChr()
{
int i=0;
for(i=0;i<n;i++)
{
Chr[i]=n;
Chr1[i]=n;
}
}
/* procedura di stampa di Chr[] */
void stampaVett()
{
int i=0;
for(i=0;i<n;i++)
printf ("%d ",Chr[i]);
printf("\n");
}
/* procedura esaustiva di calcolo soluzioni */
/* metto 0 nella prima posizione e generola permutazione su 1 2,
poi metto 1 nella prima posizione e genero la permutazione su 0 2,
ed infine metto 2 nella prima posizione e genero la permutazione su 0 1 , */
void genTPerm(int k)
{
int i=0;
if(k>(n-1))
{
stampaVett();
/* verifica se la soluzione trovata è un ciclo: se si succ=1 e termina genTPerm */
nChr++;
if(nChr>n)
{
Succ=0;
return ;
}
}
else
for(i=0;i<n;i++)
{if(Chr1[i]==n)
{Chr[k]=i;
Chr1[i]=k;
genTPerm(k+1);
Chr1[i]=n;
Chr[k]=n;
}
}
}
/* programma principale */
int main(void)
{
int i=0, k=0;
/* inizializza variabili, vettori e strutture dati */
nChr = 0;
initChr(); /* procedura che inizializza Chr e Chr1 */
genTPerm(0); /* procedura esaustiva per il calcolo di soluzioni */
}
Questo è il codice di un grafo con lista di adiacenza viene eseguito però non so se va bene:
#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);
}