CODEWITHSUNDEEP
c
giacomotb
giacomotb

Reputation: 607

Depth-first search in graph

I'm writing a graph data-structure myself just to learn how it works. But, the depth-first search is not working properly, and I don't know why. I think there is a problem with the pointers, but I can't find it.

Can someone help me? Here is the code of the method:

void VisitaInProfondita(GrafoMatrice *grafo, TipoNodo nodo_iniz){
     TipoNodo i, j;
     bool nodi_visitati[NumNodi];
     PilaElem *nodi_da_visitare;

     for(i=0; i<NumNodi; i++)
           nodi_visitati[i] = false;

     InitPila(&nodi_da_visitare);
     Push(&nodi_da_visitare, nodo_iniz);

     while(!TestPilaVuota(nodi_da_visitare)){
           Pop(&nodi_da_visitare, &i);

           if(!nodi_visitati[i]){
                printf(" %d ", i);
                nodi_visitati[i] = true;
                for (j=NumNodi-1; j>=0; j--)
                     if(TestEsisteArcoMatrice(grafo, i, j) && !nodi_visitati[i])
                          Push(&nodi_da_visitare, j);
           }
     }
}

And here there is my stack file:

typedef int TipoElemPila;
typedef struct PilaElem *TipoPila;

typedef struct PilaElem{
        TipoElemPila val;
        struct PilaElem *next;
        }PilaElem;

void InitPila(PilaElem **p){
     *p = NULL;
}

bool TestPilaVuota(PilaElem *p){
     return p == NULL;
}

void TopPila(PilaElem *p, TipoElemPila *v){
     if(TestPilaVuota(p))
          printf("ERRORE: PILA VUOTA\n");
     else
          *v = p->val;                          
}

void Push(PilaElem **p, TipoElemPila v){
     PilaElem *paux;
     paux = (PilaElem *)malloc(sizeof(struct PilaElem));
     paux->val = v;
     paux->next = *p;
     *p = paux;
}

void Pop(PilaElem **p, TipoElemPila *v){
     PilaElem *paux;
     if(TestPilaVuota((*p)))
          printf("ERRORE: PILA VUOTA\n");
     else{
          *v = (*p)->val;
          paux = *p;
          *p = (*p)->next;
          free(paux);
     }
}

Thank you for helping me!

Upvotes: 0

Views: 369

Answers (2)

Henrik
Henrik

Reputation: 23324

This looks strange:

            nodi_visitati[i] = true;
            for (j=NumNodi-1; j>=0; j--)
                 if(TestEsisteArcoMatrice(grafo, i, j) && !nodi_visitati[i])

should probably be

                 if(TestEsisteArcoMatrice(grafo, i, j) && !nodi_visitati[j])

Upvotes: 2

Joni
Joni

Reputation: 111219

You could benefit from better naming conventions. Here you check if the current node has not been visited yet, and it has, so you never enter the "then" branch:

if(TestEsisteArcoMatrice(grafo, i, j) && !nodi_visitati[i])

(i should be j)

There could be other mistakes, I haven't read the whole thing.

Upvotes: 2

Related Questions