title: How to find if a graph contains a cycle using a recursive DFS?
body: <p>The code below is an implementation of a depth-first
   search DFS to determine if a directed graph has a cycle or not. However, there appears to be a bug in it as it's not working. I'm almost 100% sure that the bug lies in <code>if (visited[w])</code> condition. My logic here is basically - if a node has already been visited, then a cycle exists. However, the problem with <code>if (visited[w])</code> is that although the condition may be true, it doesn't necessarily mean that there is a cycle, as the node may have been visited long ago. </p>
  
  <pre><code>int *visited;  // array [0..V-1] of booleans
  
  int checkCycle(Graph g)
  {
     visited = malloc(sizeof(int)*g-&gt;numVertices);
     int result = dfsCycleCheck(g, 0);
     free(visited);
     return result;
  }
  int dfsCycleCheck(Graph g, Vertex v)
  {
     visited[v] = 1;
     Vertex w;
     for (w = 0; w &lt; nV(g); w++) {
        if (!hasEdge(g,v,w)) continue;
        if (visited[w]) return 1; // found cycle
        return dfsCycleCheck(g, w);
     }
     return 0; // no cycle
  }
  </code></pre>