CODEWITHSUNDEEP
cyclegraph-algorithmdepth-first-search
Lipika Deka
Lipika Deka

Reputation: 3884

Output the nodes in a cycle existing in a directed graph

While I understand that we can detect cycles with the DFS algorithm by detecting back-edges http://cs.wellesley.edu/~cs231/fall01/dfs.pdf. I am not being able to figure out how to output the nodes in the cycle in an efficient and "clean" manner while following the above said method.

Would be gratfeull for some help

Thanks

Upvotes: 0

Views: 369

Answers (1)

pokey909
pokey909

Reputation: 1837

This is how i did it in my own implementation. It deviates a little bit in the naming conventions from the one used in your PDF but it should be obvious what it does. All m_* variables are vectors, except m_topoOrder and m_cycle which are stacks. The nodes of the cycle will be in m_cycle. The m_onStack keeps track of nodes which are on the recursive call stack.

For a complete description i suggest the book Algorithms by Robert Sedgewick.

void QxDigraph::dfs(int v)
{
    m_marked[v] = true;
    m_onStack[v] = true;

    foreach(int w, m_adj[v]) {
        if(hasCycle()) return;
        else if(!m_marked[w])
        {
            m_edgeTo[w] = v;
            dfs(w);
        }
        else if(m_onStack[w])
        {
            m_cycle.clear();
            for(int x=v; x!=w; x = m_edgeTo[x])
                m_cycle.push(x);
            m_cycle.push(w);
            m_cycle.push(v);
        }
    }
    m_onStack[v] = false;
    m_topoOrder.push(v);
}

Upvotes: 0

Related Questions