Finding a cycle in a directed graph using BFS or DFS

Question

I tried looking around the Internet but I'm a little stuck at the moment with regards to modifying the BFS or DFS algorithm in order to be able to find a cycle in a directed graph. If the graph were not directed, the DFS algorithm would solve this using back edges, but this method fails when looking at directed graphs.

Can anyone point me in the right direction? Thanks for your time.

Answer 1

DFS algorithm classifies graph edges into three categories ^*:

• Forward edges
• Cross edges
• Back edges

If your graph has a back edge, it has a cycle. When you run a DFS algorithm and see a backedge, examine the portion of the path from the vertex to which the back edge leads to the current node will give you a set of nodes from the cycle to which the back edge belongs.

^* Sometimes, tree edges are treated as a separate category from forward edges, which is insignificant for the purposes of this discussion.

Answer 2

Keep track of vertices currently in recursion stack of function for DFS traversal. If you reach a vertex that is already in the recursion stack, then there is a cycle in the tree.

Create an array recStack[] and add every vertex visited in it. if you encounter a vertex that is already visited, there exists a cycle and you can print it by passing that vertex again to a modified DFS function for printing

bool isGraphCyclic(int v, bool visited[], bool *recStack)
{
    if(visited[v] == false)
    {
        // Mark the current node as visited and part of recursion stack
        visited[v] = true;
        recStack[v] = true;

        // Recur for all the vertices adjacent to this vertex
        list<int>::iterator i;
        for(i = adj[v].begin(); i != adj[v].end(); ++i)
        {
            if ( !visited[*i] && isGraphCyclic(*i, visited, recStack) )
                return true;
            else if (recStack[*i])
                return true;
        }

    }
    recStack[v] = false;  // remove the vertex from recursion stack
    return false;
}