在无向图中以O(n)的复杂度查找并打印简单环的算法

Question

给定无向图 graph G(V,E)。在 IT 技术中使用。

|E| = m, |V| = n 

图的数据结构是邻接表。

如何在O(n)复杂度内查找和打印简单循环（或打印没有这样的循环）？（如果存在循环，则输出应该是循环中包含的顶点列表。）

我知道如何在O(n)复杂度内查找循环，互联网上也有指南。我的问题是如何打印它。

这是我尝试做的：

DFS-CheckCycle ( Graph G)
{
    p[] <- null //parent array
    foreach v in V
        Color[u] <- white

    foreach v in V
    {
        if (Color[u] = white) 
            Visit(u)
    }
}

Visit(Vertex u)
{
    bool Cycle <- false;
    Color[u] <- gray
    foreach v in Adj[u]
    {
        p[v] <- u
        if (Color[v] = white)
            Visit(v);
        else if (Color[v] = gray) 
        {
            Cycle <- true;
            break;
        }
    }

    if(!Cycle)
        print "No Cycle"
    else
        PrintCycle(v,u)
}



PrintCycle(Vertex v, Vertex u)
{
    if(v = u)
        print v;
    else
    {
        print v;
        PrintCycle(p[v], u);
    }
}

请记住，它需要是 O(n) 的复杂度。

我的 PrintCycle 函数没有打印所有的顶点。

我需要一些帮助来打印我找到的循环中的顶点。

- E235

---

谷歌搜索“弗洛伊德算法”（但您的着色方法同样有效）。顺便说一句，您可以存储从起始点跳数的数字（也许是访问此节点的节点）。 - wildplasser

我没有阅读你的代码，但如果深度优先搜索被正确使用，它应该构建存储数组（每个节点及其父节点），使用此数组来重构你的路径。 - user1935024

@G.Bach 我认为他假设顶点数大于边数，因此几乎是O(2n) = O(n)。但正如你所说，我也知道它是O(n+m)。 - user1935024

@wildplasser，弗洛伊德算法在这里对我没有帮助。它在最坏情况下的复杂度是n^3。 - E235

如果至少有n条边，那么一定存在一个环（因为最大无环图是一棵树，它有n-1条边）。这意味着您可以丢弃除前n条边以外的所有边，结果图将具有环当且仅当原始图形具有环。因此，您不需要担心m。 - Paul Hankin

Answer 1

我注意到你算法中有两个问题。首先，在使用DFS遍历时，你应该保持以下不变量：

1. 未访问的顶点应涂成白色（你已经做到了）；
2. 已访问的顶点，在 Visit() 方法尚未结束时应该涂成灰色；
3. 已访问的顶点，在 Visit() 方法已经返回后应该涂成黑色（或其他颜色，除了灰色和白色）。

另一个我注意到的问题是你没有正确为节点分配父节点。在你的 Visit() 方法中，即使我们要访问的下一个顶点已经是灰色的，也会进行父节点的赋值，也就是说它已经在DFS树中有了父节点。

因此，我会相应地更改你的代码：

DFS-CheckCycle ( Graph G)
{
    p[] <- null //parent array
    foreach v in V
        Color[v] <- white

    foreach u in V
    {
        if (Color[u] = white) {
            p[u] <- -1; // meaning it is a root of a DFS-tree of the DFS forest
            Visit(u)
        }
    }
}

Visit(Vertex u)
{
    bool Cycle <- false;
    Color[u] <- gray
    foreach v in Adj[u]
    {
        if (Color[v] = white) {
            p[v] <- u
            Visit(v);
        }
        else if (Color[v] = gray) 
        {
            Cycle <- true;
            break;
        }
    }
    Color[u] <- black; // once DFS for this vertex ends, assign its color to black

    if(!Cycle)
        print "No Cycle"
    else
        PrintCycle(v,u)
}



PrintCycle(Vertex v, Vertex u)
{
    if(v = u)
        print v;
    else
    {
        print v;
        PrintCycle(p[v], u);
    }
}

编辑：将您的PrintCycle方法改为非递归方法可能是一个好主意：

PrintCycle(Vertex v, Vertex u) 
{
    do {
        print u;
        u = p[u];
    } while (u != v);
}

- kt-9

---

你的非递归 PrintCycle 是 不正确 的。它将无法打印 v，即使它在循环中（仅当 u == v 时才会打印 v）。 - Md. Abu Nafee Ibna Zahid

Answer 2

在递归搜索中，您可以添加一个参数，它是祖先节点链，一直到搜索根节点。循环将包括当前节点和链中的节点，以灰色节点结束，以发现循环。

链是指lisp风格的列表：一个由节点和另一个成对出现的节点组成的对，最后一个对为空。

更直接的方法是使用显式堆栈而不是递归进行搜索。堆栈上的节点都是灰色的。当您找到表示循环的灰色节点时，可以通过从堆栈反向工作来打印循环。

- Gene

---

但是堆栈的想法存在问题，尽管我喜欢它。 如果在开始时我经过孤立的顶点a并将其添加到堆栈中。 当我找到一个循环时，我会打印堆栈，但它也会打印孤立的顶点，这不好。 我只需要打印我发现的循环中的顶点。 - E235

@EviatarG。我不知道你所说的孤立顶点是什么意思。如果你找到了一个环，那么环的定义直接意味着这个环必须在堆栈上。如果一个顶点有一条连接它自身的边，那仍然是一个环。 - Gene

好的，你的建议是在DFS-CheckCycle的开头添加“Stack stack;”，并在Visit函数中在“if(Color[v] =white)”语句下方添加“stack.Push(v)”？ 当我发现一个循环时只需打印它？ - E235