Modifica codice in C con lista di adiacenza

[mikael_c]

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