使用DFS检查无向图中的循环？

Question

因此，我为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;
}   

但是，我的检查周期函数返回true，即使他们没有周期。那是为什么呢？我的功能有问题吗？没有执行问题，否则我早就调试了，但他们似乎在我的逻辑中有问题。

Answer 1

在检查周期开始之前，arr[]中的所有bools都设置为false吗？

您确定节点的迭代器没有在已经遍历的边上加倍（从而多次看到起始节点，而不考虑循环）？

Answer 2

请注意，您的函数并不像您认为的那样。让我来看看这里发生了什么。假设以下关系：（1,2）、（1,3）、（2,3）。我并没有假设反射性（即，（1,2）并不意味着（2,1））。关系是定向的。

1. 从节点1开始。将其标记为已访问

您需要一堆已访问的节点，或者只搜索原始节点。堆栈也将检测子循环（不包括原始节点的循环），但它也会占用更多内存。

编辑：节点堆栈不仅仅是一堆true/false值，而是节点编号的堆栈。当前堆栈跟踪中已访问的节点（如果该节点存在于堆栈中）。

然而，还有一种更有利于内存的方法：在调用结束时设置arr[foo]=false；。像这样的东西：

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;
}   

我想应该够了。

编辑：现在应该支持无向图。节点：此代码未测试

编辑：有关详细的解决方案，请参见强连接组件

编辑：尽管在评论中给出了具体的解决方案，但这个答案是市场所接受的。阅读评论了解详细信息。