c - 图中的深度优先搜索

Question

我正在自己编写图形数据结构，只是为了了解它是如何工作的。但是，深度优先搜索无法正常工作，我不知道为什么。我认为指针有问题，但我找不到它。

有人可以帮助我吗？这是该方法的代码:

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

这是我的堆栈文件:

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

谢谢你帮助我!

Answer 1

您可以从更好的命名约定中获益。在这里你检查 current 节点是否还没有被访问过，并且它已经访问过，所以你永远不会进入“then”分支:

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

(我应该是j)

可能还有其他错误，我没看完。