因此,我为 DFS 编写了以下代码:
void dfs (graph * mygraph, int foo, bool arr[]) // here, foo is the source vertex
{
if (arr[foo] == true)
return;
else
{
cout<<foo<<"\t";
arr[foo] = true;
auto it = mygraph->edges[foo].begin();
while (it != mygraph->edges[foo].end())
{
int k = *it;
if (arr[k] == false)
{
//cout<<k<<"\n";
dfs(mygraph,k,arr);
//cout<<k<<"\t";
}
it++;
}
}
//cout<<"\n";
}
现在,我在一个无向图中读到,如果在 DFS 时,它再次返回到同一个顶点,则存在一个循环。因此,我所做的是这样的,
bool checkcycle( graph * mygraph, int foo, bool arr[] )
{
bool result = false;
if (arr[foo] == true)
{
result = true;
}
else
{
arr[foo] = true;
auto it = mygraph->edges[foo].begin();
while (it != mygraph->edges[foo].end())
{
int k = *it;
result = checkcycle(mygraph,k,arr);
it++;
}
}
return result;
}
但是,即使它们不是循环,我的 checkcycle 函数也会返回 true。这是为什么?我的功能有问题吗?没有执行问题,否则我会调试,但他们的逻辑似乎有问题。
最佳答案
请注意,您的函数并不完全按照您的想法进行。让我尝试逐步了解这里发生的事情。假设以下关系:(1,2)、(1,3)、(2,3)。我不假设反射性(即 (1,2) 并不意味着 (2,1))。关系是定向的。
- 从节点 1 开始。将其标记为已访问
- 迭代它的 child (2 和 3)
- 在节点2时,递归调用
校验循环
。此时 2 也被标记为已访问。 - 递归调用现在访问 3(深度搜索)。 3 也被标记为已访问
- 调用步骤 4 时返回
false
- 调用步骤 3 时返回
false
- 我们回到第 2 步。现在我们将迭代节点 3,它已在第 4 步中被标记。它只返回
true
。
你需要一堆访问过的节点或者你只搜索原始节点。堆栈也会检测子循环(不包括原始节点的循环),但它也会占用更多内存。
编辑:节点堆栈不仅仅是一堆 true
/false
值,而是一堆节点号。如果某个节点存在于堆栈中,则该节点已在当前堆栈跟踪中被访问。
然而,有一种更利于内存的方法:设置 arr[foo] = false;
as the calls die。像这样:
bool checkcycle( graph * mygraph, int foo, bool arr[], int previousFoo=-1 )
{
bool result = false;
if (arr[foo] == true)
{
result = true;
}
else
{
arr[foo] = true;
auto it = mygraph->edges[foo].begin();
while (it != mygraph->edges[foo].end())
{
int k = *it;
// This should prevent going back to the previous node
if (k != previousFoo) {
result = checkcycle(mygraph,k,arr, foo);
}
it++;
}
// Add this
arr[foo] = false;
}
return result;
}
我觉得应该够了。
编辑:现在应该支持无向图。 节点:此代码未经测试
编辑:有关更详细的解决方案,请参阅 Strongly Connected Components
编辑:虽然评论中给出了具体的解决方案,但这个答案已被市场接受。阅读评论了解详情。
关于c++ - 使用 DFS 检查无向图中的循环?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/31526279/