使用 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 时，它再次 returns 到同一个顶点，就有一个循环。所以，我的做法是这样的，

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 函数 returns 即使它们不是循环也是如此。这是为什么？我的功能有问题吗？没有执行问题，否则我会调试，但他们的逻辑似乎有问题。

Answer 1

在 checkcycle 开始之前，arr[] 中的所有布尔值都设置为 false 了吗？

你确定你的节点迭代器没有在它已经遍历的边上加倍返回（因此无论循环如何多次看到起始节点）？

Answer 2

请注意，您的函数并不像您认为的那样。让我尝试逐步了解这里发生的事情。假设以下关系：(1,2)、(1,3)、(2,3)。我不假设反射性（即 (1,2) 并不意味着 (2,1)）。关系是定向的。

从节点 1 开始。将其标记为已访问
迭代其子项（2 和 3）
在节点2时，递归调用check cycle。此时 2 也被标记为已访问。
递归调用现在访问 3（深度搜索）。 3 也被标记为已访问
第 4 步的调用已返回 false
第 3 步的调用在返回时死亡 false
我们回到第 2 步。现在我们将迭代节点 3，它已在第 4 步中标记。它只是 returns true.

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

编辑：节点堆栈不仅仅是一堆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;
}

我觉得应该够了。

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

编辑：有关更详细的解决方案，请参阅 Strongly Connected Components

编辑：尽管评论中给出了具体解决方案，但该答案已被市场接受。阅读评论了解详情。

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

Checking for a cycle in an undirected graph using DFS?

c++

graph

depth-first-search