我正在尝试使用 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]);
}
最佳答案
我找到了解决方案。这是算法
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);
}
}
}
}
}
关于c - 来自 DFS 的生成树导致错误的值,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/18950915/