在无向图上查找和打印O（n）复杂度简单循环的算法 [英] Algorithm to find and print simple cycle in complexity of O(n) on undirected graph

问题描述

给出图G（V，E），无向图。

|E| = m, |V| = n 

该图的数据结构为邻接列表

The graph's data structure is Adjacency list

如何查找和打印复杂度为 O（n）的简单循环（或打印没有这样的循环）？

（如果有循环，输出应该是循环的一部分的顶点列表。）

How to find and print simple cycle (or print that there is no such cycle) in complexity of O(n)?
(If there is cycle the output should be the list of vertex that are part of the cycle.)

我知道如何根据 O的复杂度找到循环（n），互联网上也有人。

我的问题是如何打印它。

I know how to find cycle on complexity of O(n), there is also gudies on the internet.
My problem is how to print it.

这是我尝试做的事情：

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

remember that it needs to be O(n).
My PrintCycle function doesn't print all the vertexes.

我需要一些帮助

推荐答案

我注意到有两件事在您的算法中似乎不正确。首先，当您使用DFS漫游时，应保持以下不变性：

I noticed two things which does not seem correct in your algorithm. Firstly, when you use your DFS walk, you should maintain the following invariant:

1. 未访问的顶点应被涂成白色； （您这样做了）


2. Visit（）尚未结束的访问顶点，应涂成灰色；
   
3. 已为其返回 Visit（）的可见顶点应涂成黑色（或彩色，而不是灰色或白色）。

1. Unvisited vertices should be painted white; (you did that)
2. Visited vertices, for which Visit() hasn't ended yet, should be painted gray;
3. Visited vertices, for which Visit() has returned should be painted black(or color, other than gray or white).

我注意到的另一件事是，您没有为节点正确分配父节点。在您的 Visit（）方法中，即使我们下一步要访问的顶点是灰色的（即在DFS树中已经有一个父级），也分配了父级。

The other thing I noticed, you don't assign parents for nodes correctly. In your Visit() method parents are assigned even if the vertex we want to visit on the next step is gray, i.e. already has a parent in DFS-tree.

所以我将相应地更改您的代码：

So I would change your code accordingly:

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 方法转换为非递归方法：

It might be a good idea to turn your PrintCycle method into non-recursive one:

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

这篇关于在无向图上查找和打印O（n）复杂度简单循环的算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！