DFS에서 스패닝 트리가 잘못된 값을 가져옴

Question

C를 사용하여 수준이있는 DFS 함수를 구현하려고하지만 루트 노드의 이웃에 레이어의 해당 값이 잘못되어 해당 항목의 잘못된 부분을 볼 수 없습니다. 암호.

1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 1;

내가 노드 4에서 DFS를 시작하면, 레이어 계산 반환 : 노드 3를 제외한 모든 노드에 대한 올바른

Marked Items: node[1] with level = 7 
Marked Items: node[2] with level = 8 
Marked Items: node[3] with level = 2 
Marked Items: node[4] with level = 1 
Marked Items: node[5] with level = 2 
Marked Items: node[6] with level = 3 
Marked Items: node[7] with level = 4 
Marked Items: node[8] with level = 5 
Marked Items: node[9] with level = 6 

, 그것은 마지막으로 레벨 9

에 있어야합니다 코드는 다음과 같습니다.

void dfsFromMatrix(uint64_t **matrix, unsigned vertexes, unsigned root) { 
    unsigned *markedItems; 
    stack *stack; 
    unsigned tempVertex; 
    unsigned i; 
    unsigned level = 1; 

#ifdef _DEBUG_ 
    printf("\n\nDFS: Start\n"); 
#endif 

    /* Alocar um vértice a mais, visto que a posição 0 não é utilizada */ 
    markedItems = (unsigned *) calloc(vertexes + 1, sizeof(unsigned)); 
    stack = NULL; 

    stack = stackPush(stack, root); 
    markedItems[root] = 1; 

#ifdef _DEBUG_ 
    printf("DFS: Starting from vertex: %u\n", root); 
    printf("DFS: Marquei o vértice raiz: %u\n", root); 
#endif 

    while (!stackIsEmpty(stack)) { 
     tempVertex = stack -> data; 
     stack = stackPop(stack); 

     printf("%u \n", tempVertex); 
     level++; 
     /* Não sei qual a diferença em inverter o loop */ 
     for (i = 1 ; i <= vertexes ; i++) 
     //for (i = vertexes ; i > 0 ; --i) 
      if (getValueFromMatrix(matrix, tempVertex, i) && !markedItems[i]) { 
       stack = stackPush(stack, i); 

       if (level != markedItems[tempVertex]+1) 
        level = markedItems[tempVertex]+1; 

       markedItems[i] = level; 


#ifdef _DEBUG_ 
       printf("DFS: Marquei o vértice %u ligado ao vértice %u\n", i, tempVertex); 
#endif 
      } 
    } 

    for (i = 1 ; i <= vertexes ; i++) 
     printf("Marked Items: node[%u] with level = %u\n",i,markedItems[i]); 

} 

Answer 1

해결책을 찾았습니다. 알고리즘은 다음과 같습니다.

void dfsFromMatrix(uint64_t **matrix, unsigned vertexes, unsigned root) { 
    unsigned *markedItems; 
    unsigned *pai; 
    stack *stack; 
    unsigned tempVertex; 
    unsigned i; 

    unsigned *level = (unsigned *) malloc((vertexes + 1) * sizeof(unsigned)); 

#ifdef _DEBUG_ 
    printf("\n\nDFS: Start\n"); 
#endif 

    /* Alocar um vértice a mais, visto que a posição 0 não é utilizada */ 
    markedItems = (unsigned *) calloc(vertexes + 1, sizeof(unsigned)); 

    /* Não preciso inicializar esse vetor */ 
    pai = (unsigned *) malloc((vertexes + 1) * sizeof(unsigned)); 

    stack = NULL; 

    stack = stackPush(stack, root); 
    level[root] = 0; 

#ifdef _DEBUG_ 
    printf("DFS: Starting from vertex: %u\n", root); 
    printf("DFS: Marquei o vértice raiz: %u\n", root); 
#endif 

    while (!stackIsEmpty(stack)) { 
     tempVertex = stack -> data; 
     stack = stackPop(stack);   
     printf("\nTirei %u da pilha!\n", tempVertex); 
     printf("%u esta com marcacao %u!\n", tempVertex, markedItems[tempVertex]); 

     printf("Vetor de Marcações:\n"); 
     for (i = 0 ; i <= vertexes ; i++) { 
      printf("markedItems[%u] = %u\n", i, markedItems[i]); 
     } 

     if (!markedItems[tempVertex]) { 
      printf("Marquei %u\n", tempVertex); 
      markedItems[tempVertex] = 1; 

      /* Não sei qual a diferença em inverter o loop */ 
      for (i = 1 ; i <= vertexes ; i++) { 
      //for (i = vertexes ; i > 0 ; --i) 

       if (getValueFromMatrix(matrix, tempVertex, i) && !markedItems[i]) { 
        stack = stackPush(stack, i); 
        printf("Coloquei %u da pilha!\n", i); 
        pai[i] = tempVertex; 
        level[i] = level[tempVertex] + 1; 
        printStack(stack); 
       } 
      } 
     } 
    } 
}