C/C++ - visita in profondità DFS

Forum - C/C++ - visita in profondità DFS

zaire90 (Normal User)
Rookie

Messaggi: 46
Iscritto: 16/10/2009

Postato alle 10:27
Venerdì, 10/02/2012

Salve,
ho scritto il programma per fare la visita DFS in profondità su un grafo, orientato o non, versione ricorsiva, come si trova su qualunque libro di informatica.
Il codice funziona, cioè esegue la visita nel modo giusto, però mi serve di memorizzare i nodi in base al loro tempo di fine visita, e ho pensato di farlo andando a mettere il relativo nodo in una pila ogni volta che la sua visita finisce (cioè il suo colore diventa BLACK, ossia 2). Però non funziona come dovrebbe:

Codice sorgente - presumibilmente C++

# include <stdlib.h>
# include <stdio.h>
 
typedef struct nodo1 {
  int info;
  struct nodo1 *next;
} NODO;
 
typedef struct nodo2 {    // Struttura per impilare i nodi in base 
  int info;                       // al loro tempo di fine visita
  struct nodo2 *next;
} LEV;  
 
typedef NODO *NODOPTR;
typedef LEV *LEVPTR;
 
int leggiGrafo(NODOPTR*);
NODOPTR leggiLista();
void visitaDFS(int,NODOPTR*,int*,int*,LEVPTR);
LEVPTR push(LEVPTR,int);
void stampa(LEVPTR);
 
int main(void)
{
  NODOPTR lisAd[20];
  LEVPTR p = NULL;
  int n, i, pred[20], color[20];
 
  n = leggiGrafo(lisAd);
 
  for(i=0; i<n; i++) {
    color[i] = 0;
    pred[i] = -1;
  }
  
  for(i=0; i<n; i++) {
    if(color[i] == 0)
      visitaDFS(i,lisAd,color,pred,p);
  }
 
  printf("\nLa visita DFS ha prodotto il seguente albero:\n");
  for(i=0; i<n; i++)
    printf("\nPadre di %d = %d",i,pred[i]);
 
  printf("\n\nLista nodi in ordine decrescente sui tempi di fine visita:\n");
  stampa(p);
 
  printf("\n\n");
  return 0;
}
 
int leggiGrafo(NODOPTR *l)
{
  int n, i;
 
  printf("\nNUMERO DI VERTICI:  ");   scanf("%d",&n);
  for(i=0; i<n; i++) {
    printf("\nLista vertici adiacenti al %d° nodo:\n",i);
    l[i] = leggiLista();
  }
 
  return n;
}
 
NODOPTR leggiLista()
{
  int x;
  NODOPTR l = NULL, app;
 
  scanf("%d",&x);
  while(x != -1) {
    app = (NODOPTR)malloc(sizeof(NODO));
    app->info = x;
    app->next = l;
    l = app;
 
    scanf("%d",&x);
  }
 
  return l;
}
 
void visitaDFS(int i, NODOPTR *l, int *color, int *pred, LEVPTR p)
{
  NODOPTR q;
 
  color[i] = 1;
 
  q = l[i];
  while(q != NULL) {
    if(color[q->info] == 0) {
      pred[q->info] = i;
      visitaDFS(q->info,l,color,pred,p);
    }
    else
      q = q->next;
  }
  color[i] = 2;
 
  p = push(p,i);
  printf("%d  ",p->info);
 
  return;
}
 
LEVPTR push(LEVPTR p, int i)
{
  LEVPTR aux;
 
  aux = (LEVPTR)malloc(sizeof(LEV));
  aux->info = i;
  aux->next = p;
  p = aux;
 
  return p;
}
 
void stampa(LEVPTR p)
{
  while(p != NULL) {
    printf("%d --> ",p->info);
    p = p->next;
  }
  printf("NULL\n\n");
  
  return;
}

cioè quello che ho fatto è stato solo di inserire l'istruzione

p = push(p,i)

nella funzione visitaDFS, per far mettere in una pila di volta in volta il nodo i, che è quello per cui la visita è finita prima.
Quindi subito sotto ho fatto stampare il valore per vedere se era corretto e funziona bene...solo che ora quando la visita finisce e si ritorna nel main la pila costruita non la prende più...e quindi arrivando all'istruzione stampa(p) mi stampa solo NULL, oppure da errore di segmentazione. Cosa c'è che non va?

nessuno (Normal User)
Guru^2

Messaggi: 6402
Iscritto: 03/01/2010

Postato alle 10:54
Venerdì, 10/02/2012

Tu passi un puntatore ad una funzione. Un puntatore il cui valore dovrà essere modificato. Ma in questo caso, dovrai passare il puntatore per puntatore per fare in modo che possa essere modificato.

In pratica dovrai passare

&p

e il parametro dovrà essere un doppio puntatore.

All'interno della funzione, modificherai il puntatore con

*p = ...

AH ok...quindi passo &p alla funzione visita e quindi dentro p diventa *p...ora mi sbaglio a scrivere la funzione push però! - zaire90 - 10/02/12 12:18

cioè come riaggiusto la funzione push? dovrò passare &p anche a lei, e poi in essa uso *p...facendolo poi anche restituire no? - zaire90 - 10/02/12 12:31

Sì ... prova e se qualcosa non funziona mostra nuovamente il codice modificato ... - nessuno - 10/02/12 13:10

Ricorda che nessuno è obbligato a risponderti e che nessuno è perfetto ...
---
Il grande studioso italiano Bruno de Finetti ( uno dei padri fondatori del moderno Calcolo delle probabilità ) chiamava il gioco del Lotto Tassa sulla stupidità.

nessuno (Normal User)
Guru^2

Messaggi: 6402
Iscritto: 03/01/2010

Postato alle 16:30
Venerdì, 10/02/2012

Per i nuovi problemi che mi hai indicato, considera che quando chiami la push non devi usare

*p = push(&p,i);

ma

*p = push(p,i);

dato che il parametro p è già un puntatore doppio.

senti scusami, il condice continua a non funzionare ache facendo cosi...scrivendo quindi: - zaire90 - 10/02/12 16:52

*p = push(p,i) come aggiusto poi la funzione push...LEVPTR* push(LEVPTR p, int i) e poi nel suo interno uso p e scrivo retun p?? perchè in ogni caso non compila - zaire90 - 10/02/12 16:54

nessuno (Normal User)
Guru^2

Messaggi: 6402
Iscritto: 03/01/2010

Postato alle 17:02
Venerdì, 10/02/2012

Non dovevi toccare il tipo di dato restituito dalla push ma solamente il suo parametro ... quindi

Codice sorgente - presumibilmente C/C++

LEVPTR push(LEVPTR *p, int i)
{
  LEVPTR aux;
 
  aux = (LEVPTR)malloc(sizeof(LEV));
  aux->info = i;
  aux->next = *p;
  *p = aux;
 
  return *p;
}

Grazie mille!! - zaire90 - 10/02/12 17:16