Clever Geek Handbook

Algorithm for searching and printing a simple cycle in complexity O (n) on an undirected graph

The specified graph G(V,E),

undirected graph.

|E| = m, |V| = n

Graph data structure is Adjacency list

How to find and print a simple cycle (or print that there is no such cycle) in complexity O(n)

?
(If there is a loop, the output must be a list of vertices that are part of the loop.)

I know how to find a cycle in difficulty O(n)

, there are homosexuals on the Internet as well.
My problem is how to print .

Here's what I tried to do:

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);
    }
}

remember what it should be O(n)

.
My PrintCycle function doesn't print all vertices.

I need help on how to print the vertices of the found loop.

+3


source to share


2 answers


I noticed two things that don't seem to be correct in your algorithm. First, when you use your DFS walk, you must maintain the following invariant:

  • Unused vertices should be painted white; (You did it)
  • Visited vertices, for which Visit()

    it is not finished yet, should be colored gray;
  • Visited vertices, for which it Visit()

    returned, should be colored black (or a color other than gray or white).

Another thing I noticed is that you have incorrectly assigned parents for the nodes. In your method, Visit()

parents are assigned even if the vertex we want to visit in the next step is gray, that is, it already has a parent in the 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);
    }
}

EDIT: It might be a good idea to turn your method PrintCycle

into a non-recursive one:

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


source


In recursive search, you can add a parameter that is a chain of ancestors up to the root of the search. The loop will consist of the current node, and in a chain ending at the gray node found to detect the loop.

By chain, I mean a list of lisp-styles: a pair consisting of a node and another pair, with the last pair being null.



An easier way is to search with an explicit stack rather than recursion. The nodes on the stack are gray. When you find a gray dial node, the loop can be printed out by traversing back through the stack.

0


source






More articles:


All Articles