Questo sito utilizza cookies, anche di terze parti, per mostrare pubblicità e servizi in linea con il tuo account. Leggi l'informativa sui cookies.
Username: Password: oppure
C/C++ - visita in profondità DFS
Forum - C/C++ - visita in profondità DFS

Avatar
zaire90 (Normal User)
Rookie


Messaggi: 46
Iscritto: 16/10/2009

Segnala al moderatore
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++

  1. # include <stdlib.h>
  2. # include <stdio.h>
  3.  
  4. typedef struct nodo1 {
  5.   int info;
  6.   struct nodo1 *next;
  7. } NODO;
  8.  
  9. typedef struct nodo2 {    // Struttura per impilare i nodi in base
  10.   int info;                       // al loro tempo di fine visita
  11.   struct nodo2 *next;
  12. } LEV;  
  13.  
  14. typedef NODO *NODOPTR;
  15. typedef LEV *LEVPTR;
  16.  
  17. int leggiGrafo(NODOPTR*);
  18. NODOPTR leggiLista();
  19. void visitaDFS(int,NODOPTR*,int*,int*,LEVPTR);
  20. LEVPTR push(LEVPTR,int);
  21. void stampa(LEVPTR);
  22.  
  23. int main(void)
  24. {
  25.   NODOPTR lisAd[20];
  26.   LEVPTR p = NULL;
  27.   int n, i, pred[20], color[20];
  28.  
  29.   n = leggiGrafo(lisAd);
  30.  
  31.   for(i=0; i<n; i++) {
  32.     color[i] = 0;
  33.     pred[i] = -1;
  34.   }
  35.  
  36.   for(i=0; i<n; i++) {
  37.     if(color[i] == 0)
  38.       visitaDFS(i,lisAd,color,pred,p);
  39.   }
  40.  
  41.   printf("\nLa visita DFS ha prodotto il seguente albero:\n");
  42.   for(i=0; i<n; i++)
  43.     printf("\nPadre di %d = %d",i,pred[i]);
  44.  
  45.   printf("\n\nLista nodi in ordine decrescente sui tempi di fine visita:\n");
  46.   stampa(p);
  47.  
  48.   printf("\n\n");
  49.   return 0;
  50. }
  51.  
  52. int leggiGrafo(NODOPTR *l)
  53. {
  54.   int n, i;
  55.  
  56.   printf("\nNUMERO DI VERTICI:  ");   scanf("%d",&n);
  57.   for(i=0; i<n; i++) {
  58.     printf("\nLista vertici adiacenti al %d° nodo:\n",i);
  59.     l[i] = leggiLista();
  60.   }
  61.  
  62.   return n;
  63. }
  64.  
  65. NODOPTR leggiLista()
  66. {
  67.   int x;
  68.   NODOPTR l = NULL, app;
  69.  
  70.   scanf("%d",&x);
  71.   while(x != -1) {
  72.     app = (NODOPTR)malloc(sizeof(NODO));
  73.     app->info = x;
  74.     app->next = l;
  75.     l = app;
  76.  
  77.     scanf("%d",&x);
  78.   }
  79.  
  80.   return l;
  81. }
  82.  
  83. void visitaDFS(int i, NODOPTR *l, int *color, int *pred, LEVPTR p)
  84. {
  85.   NODOPTR q;
  86.  
  87.   color[i] = 1;
  88.  
  89.   q = l[i];
  90.   while(q != NULL) {
  91.     if(color[q->info] == 0) {
  92.       pred[q->info] = i;
  93.       visitaDFS(q->info,l,color,pred,p);
  94.     }
  95.     else
  96.       q = q->next;
  97.   }
  98.   color[i] = 2;
  99.  
  100.   p = push(p,i);
  101.   printf("%d  ",p->info);
  102.  
  103.   return;
  104. }
  105.  
  106. LEVPTR push(LEVPTR p, int i)
  107. {
  108.   LEVPTR aux;
  109.  
  110.   aux = (LEVPTR)malloc(sizeof(LEV));
  111.   aux->info = i;
  112.   aux->next = p;
  113.   p = aux;
  114.  
  115.   return p;
  116. }
  117.  
  118. void stampa(LEVPTR p)
  119. {
  120.   while(p != NULL) {
  121.     printf("%d --> ",p->info);
  122.     p = p->next;
  123.   }
  124.   printf("NULL\n\n");
  125.  
  126.   return;
  127. }



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?


...La saggezza di un singolo somiglia ad un albero conficcato alla meno peggio nel terreno...( HAGAKURE, codice 15)
PM
Avatar
nessuno (Normal User)
Guru^2


Messaggi: 5475
Iscritto: 03/01/2010

Up
0
Down
V
Segnala al moderatore
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 ...
PM
Avatar
nessuno (Normal User)
Guru^2


Messaggi: 5475
Iscritto: 03/01/2010

Up
0
Down
V
Segnala al moderatore
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


Ricorda che nessuno è obbligato a risponderti e che nessuno è perfetto ...
PM
Avatar
nessuno (Normal User)
Guru^2


Messaggi: 5475
Iscritto: 03/01/2010

Up
0
Down
V
Segnala al moderatore
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++

  1. LEVPTR push(LEVPTR *p, int i)
  2. {
  3.   LEVPTR aux;
  4.  
  5.   aux = (LEVPTR)malloc(sizeof(LEV));
  6.   aux->info = i;
  7.   aux->next = *p;
  8.   *p = aux;
  9.  
  10.   return *p;
  11. }




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


Ricorda che nessuno è obbligato a risponderti e che nessuno è perfetto ...
PM