DFS 스택에 두 번 입력하는 정점

Question

무 디렉션 그래프에서 DFS 구현을 디버깅하는 중 문제가 발생했습니다.

실행 중에 정점 1이 스택에 두 번 입력되어서 왜 이런 일이 발생했는지 정말로 알 수 없습니다.

여기 제 기능을 부착 해요 : [정보

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

    markedItems = (unsigned *) calloc(vertexes, sizeof(unsigned)); 
    stackPointer = NULL; 

    stackPointer = stackPush(stackPointer, root); 

    while (!checkIfStackIsEmpty(stackPointer)) { 
     tempVertex = stackPointer -> data; 

#ifdef _DEBUG_ 
    printf("tempVertex = %u\n", tempVertex); 
#endif 

     stackPointer = stackPop(stackPointer); 
     if (!markedItems[tempVertex]) { 
      markedItems[tempVertex] = 1; 

#ifdef _DEBUG_ 
      printf("DFS: Marquei o vértice %u\n", tempVertex); 
      printStack(stackPointer); 
#endif 

      for (i = 1 ; i <= vertexes ; i++) 
       if (getValueFromMatrix(matrix, tempVertex, i)) { 
        stackPointer = stackPush(stackPointer, i); 
        printf("Entrei na fila: %u\n", i); 
       } 

     } 
    } 
} 

를 루프. 그것은 실제로 하나에서 시작하여 < = 정점으로 끝납니다. getValueFromMatrix 함수가 이것을 처리하므로 인간이 이해할 수있는 행렬 위치를 사용할 수 있습니다.

어떤 도움을 주셔서 감사합니다,

Answer 1

하나의 정점과 루프 가장자리로 그래프를 가져옵니다. 알고리즘은 루트를 푸시하고 표시 한 다음 표시되어 있는지 확인하지 않고 진행중인 모든 정점을 푸시합니다. 유일한 버텍스는 자체에 연결되어 있으므로 두 번째로 밀어 넣습니다.

표준 DFS 알고리즘

는 표시되지 않은 정점을 밀어 :

pop top vertex T 
for all vertex V connected to T 
    if V is not marked 
     mark V 
     push V 
     process V 

는 마크, 푸시을 관찰하고 과정은 모두 같은 시간에 수행됩니다. 귀하의 경우, 프로세스 단계는 단지 정점을 인쇄하지만 아무것도 될 수 있습니다. 버전 마크와 푸시에서

pop top vertex T 
if T is not marked 
    mark T 
    for all vertex V connected to T   
    push V 
    process V 

가 구분됩니다

귀하의 알고리즘이 표시되지 않은 정점에 연결되어 정점을 푸시합니다. 푸시 단계 대신에 마크 단계 옆에서 프로세스 단계를 이동하면 작동 할 수 있습니다.

pop top vertex T 
if T is not marked 
    mark T 
    process T 
    for all vertex V connected to T   
    push V 

표준 알고리즘이 일반적으로 약간 더 빠르기 때문에 선호됩니다.