0

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

有人能帮我吗？这是该方法的代码：

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

感谢你们对我的帮助！

4

2 回答 2

2

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

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

（我应该是 j）

可能还有其他错误，我还没有阅读全文。

于 2013-08-13T13:43:16.517 回答
2

这看起来很奇怪：

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

应该是

                 if(TestEsisteArcoMatrice(grafo, i, j) && !nodi_visitati[j])
于 2013-08-13T13:43:32.420 回答