首页 文章

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

提问于
浏览 次
3

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

|E| = m, |V| = n

图的数据结构是邻接列表

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

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

这就是我试图做的事情：

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函数不会打印所有顶点 .

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

algorithm graph-algorithm depth-first-search

2 回答

  • 0

    在递归搜索中，您可以添加一个参数，该参数是祖先的链，一直到搜索根 . 循环将由当前节点和链中的那些节点组成，这些节点在找到循环的灰色节点处结束 .

    通过链我的意思是一个lisp风格的列表：一对由一个节点和另一对组成，最后一对是null .

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

    回复于
  • 5

    我注意到你的算法中有两件似乎不正确的事情 . 首先，当您使用DFS walk时，应该保持以下不变量：

    • 未访问的顶点应涂成白色; （你做到了）

    • Visit() 尚未结束的访问顶点应涂成灰色;

    • 已返回 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);
}
    回复于

相关问题