iamdumb's blog

cycle detection in graph.
By iamdumb, history, 9 years ago, In English

Hello everyone,Can you assist me ? I want code(c++) for cycle detection in graph using recursive dfs.I know there are many resources available out there but either they are not well explained or too Hi-fi for me.It would be best if you can add some comments if possible.

P.S : I know union find Data structure but still I would like to know some more application of dfs.Please help me in this regard

  • Vote: I like it
  • -3
  • Vote: I do not like it

»
9 years ago, # |
← Rev. 2   Vote: I like it +4 Vote: I do not like it

For cycle detection... i have a best approach of dfs. Do refer to this question. I have done cycle detection using dfs keeping record of from which x and y they are called .

int dx[] = {1,-1,0,0} ;
int dy[] = {0, 0, 1,-1};
void dfs(int i,int j,int x,int y,char c)
{
    int u;
    if(i<0 || i>=n || j<0|| j>=m) // checking for outer bounds
    return ;
    if(ch[i][j]!=c) // if not same color 
    return ;
    if(v[i][j]==true) // if you reach to any point which is already visited then cycle is detected
    {
        final = 1; // make your mark using any global varible
        return;
    }
    v[i][j] = true;
    rep(u,0,4)
    {
        int nx = i+dx[u];
        int ny = j+dy[u];
        if(nx==x && ny==y) // if nx and ny are not equal to x and y from which they are called, then call dfs.
        continue;
        else
        dfs(nx,ny,i,j,c);
    }
    return ;
}

for complete code refer here

→ Reply