在无向图上查找和打印O(n)复杂度的简单周期的算法

E23*_*235 3 algorithm depth-first-search graph-algorithm

给出graph G(V,E),无方向图.

|E| = m, |V| = n 
Run Code Online (Sandbox Code Playgroud)

图的数据结构是邻接列表

如何在复杂性中找到并打印简单循环(或打印没有这样的循环)O(n)
(如果有循环,则输出应该是循环的顶点列表.)

我知道如何找到复杂性的循环O(n),互联网上也有gudies.
我的问题是如何打印它.

这就是我试图做的事情:

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);
    }
}
Run Code Online (Sandbox Code Playgroud)

记住它需要O(n).
我的PrintCycle函数不会打印所有顶点.

我需要一些帮助如何打印我发现的循环的顶点.

kt-*_*t-9 5

我注意到你的算法中有两件似乎不正确的事情.首先,当您使用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);
    }
}
Run Code Online (Sandbox Code Playgroud)

编辑:将您的PrintCycle方法转换为非递归方法可能是个好主意:

PrintCycle(Vertex v, Vertex u) 
{
    do {
        print u;
        u = p[u];
    } while (u != v);
}
Run Code Online (Sandbox Code Playgroud)