c - 来自 DFS 的生成树导致错误的值

Question

我正在尝试使用 C 实现具有层级的 DFS 函数，但是层中的相应值在根节点的邻居中不正确，我看不出代码有什么问题。

让我们考虑以下圆图:1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 1;

当我从节点4开始DFS时，层计算返回:

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

这对所有节点都是正确的，除了节点 3，它应该在级别 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);
                }
            }
        }
    }
}