我在无向图中调试 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);
}
}
}
}
关于for循环。它实际上从 1 开始并以 <= 顶点结束。 getValueFromMatrix 函数处理这个问题,因此我可以使用人类可理解的矩阵位置。
感谢您的帮助,
最佳答案
取一张有一个顶点和一条循环边的图。您的算法会推送根,对其进行标记,然后继续推送与其连接的所有顶点,而不检查它们是否已标记。唯一的顶点与其自身相连,因此第二次被推送。
标准 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
首选标准算法,因为它通常应该稍快一些。
关于c - 顶点两次进入 DFS 堆栈,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/18929572/