c++ - 使用 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;
}   

但是，即使它们不是循环，我的 checkcycle 函数也会返回 true。这是为什么？我的功能有问题吗？没有执行问题，否则我会调试，但他们的逻辑似乎有问题。

Answer 1

请注意，您的函数并不完全按照您的想法进行。让我尝试逐步了解这里发生的事情。假设以下关系:(1,2)、(1,3)、(2,3)。我不假设反射性(即 (1,2) 并不意味着 (2,1))。关系是定向的。

1. 从节点 1 开始。将其标记为已访问
2. 迭代它的 child (2 和 3)
3. 在节点2时，递归调用校验循环。此时 2 也被标记为已访问。
4. 递归调用现在访问 3(深度搜索)。 3 也被标记为已访问
5. 调用步骤 4 时返回 false
6. 调用步骤 3 时返回 false
7. 我们回到第 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

编辑:虽然评论中给出了具体的解决方案，但这个答案已被市场接受。阅读评论了解详情。