CODEWITHSUNDEEP
c++algorithmgraph-theorydepth-first-search
Vipul
Vipul

Reputation: 819

detect cycle in directed graph with non-recursive dfs

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;

}

Upvotes: 3

Views: 5856

Answers (1)

gimme_danger
gimme_danger

Reputation: 798

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

Upvotes: 17

Related Questions