detect cycle in directed graph with non-recursive dfs

Question

My code is working but not for all test cases.

What I am trying to do here is creating a 'boolean ifparent array' which holds the record of the path I am traversing through.

'boolean visited array' keeps record of all the visited vertices.

I am using a stack for DFS.

//v is no of vertex, adj[] is the adjacency matrix
bool isCyclic(int v, vector<int> adj[])
{
    stack<int> st;
    st.push(0);

    vector<bool> visited(v, false);
    vector<bool> ifparent(v, false);
    int flag= 0;

    int s;
    while(!st.empty()){
        s= st.top();
        ifparent[s]= true;
        visited[s]=true;
        flag=0;

        for(auto i: adj[s]){
            if(visited[i]){
                if(ifparent[i])
                    return true;
            }
            else if(!flag){
                st.push(i);
                flag= 1;
            }
        }

        if(!flag){
            ifparent[s]= false;
            st.pop();
        }
    }

    return false;

}

Which cases are not working? For those cases, what is the actual result, and what is the expected result? — JaMiT, May 26 '19 at 22:07
@JaMiT [link](https://practice.geeksforgeeks.org/problems/detect-cycle-in-a-directed-graph/1) this is link to the problem. — Vipul, May 27 '19 at 05:15
Questions should be self-contained and not rely on external links for key information. Please edit the question to explain which cases are not working, what the actual results are in those cases, and what the expected results are in those cases. — JaMiT, May 27 '19 at 20:21

gimme_danger · Accepted Answer · 2019-05-27T07:53:27.187

16

If you like an iterative approach of cycle detection with DFS, I will recommend you a little reorganized version of your code, where I write DFS in a more common manner.

bool isCyclic(int V, vector<int> adj[]) {
  vector<bool> visited (V, false);
  vector<bool> on_stack (V, false);
  stack<int> st;

  for (int w = 0; w < V; w++) {

    if (visited[w])
      continue;
    st.push(w);

    while (!st.empty()) {
      int s = st.top();

      if (!visited[s]) {
        visited[s] = true;
        on_stack[s] = true;
      } else {
        on_stack[s] = false;
        st.pop();
      }

      for (const auto &v : adj[s]) {
        if (!visited[v]) {
          st.push(v);
        } else if (on_stack[v]) {
          return true;
        }
      }
    }
  }
  return false;
}

edited May 27 '19 at 07:53

answered May 26 '19 at 20:54

gimme_danger

788
1
6
14

if (!visited[v]) { no_unseen_adjacent = false; st.push (v); } This block will push every adjacent node in the stack and it wii no longer be DFS. – Vipul May 26 '19 at 21:33
Pushing all adjacent nodes doesn`t ruin dfs traversing. It is only about order of nodes visiting. In fact recursive and iterative approaches have [different order](https://stackoverflow.com/questions/9201166/iterative-dfs-vs-recursive-dfs-and-different-elements-order) . Anyway, there was a bug in my code, i have fixed it and checked the new code on the [link](https://practice.geeksforgeeks.org/problems/detect-cycle-in-a-directed-graph/) you provided. Now testing system accepts it. – gimme_danger May 27 '19 at 07:52
1

Your code was helpful. I found out that I was not considering the case of disconnected graphs. – Vipul May 27 '19 at 18:14
Consider recursive version of cycle detection algorithm as well. I think it is more intuitive. Here is the [link](https://algs4.cs.princeton.edu/42digraph/DirectedCycle.java.html) with good implementation. – gimme_danger May 27 '19 at 19:56

detect cycle in directed graph with non-recursive dfs

1 Answers1