aajjbb's blog

How to check cycles inside a Topological Sort
By aajjbb, 12 years ago, In English

Hi, I'm in doubt in how to check if there's cycles in a graph meanwhile I do a topological sort.

The only way to implement a topological sort is this one:

void dfs(int x) {
    vis[x] = true;
    for(int u = 0; u < n; u++) {
        if(!vis[u] && graph[x][u] == 1) {
            dfs(u);
        }
    }
    order.push_back(x);
}

but this implementation doesn't check if there's cycles, which modification can I do to check for cycles ?

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

Comments Comments (12)
| Write comment?
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

You may topsort this way and then, check every edge, that it's from left to right

→ Reply
»
12 years ago, # |
← Rev. 4   Vote: I like it 0 Vote: I do not like it 
void dfs(int x, int parent) {
    vis[x] = true;
    inStack[x] = true;
    for(int u = 0; u < n; u++) {
        if (graph[x][u] == 1 && u != parent && vis[u] && inStack[u]) {
            // there is a cycle: u -> ... -> parent -> x
        }
        if(!vis[u] && graph[x][u] == 1) {
            dfs(u, x);
        }
    }
    inStack[x] = false;
    order.push_back(x);
}

Ooops, it works only for undirected graphs :)
If graph is directed, you should also check if next vertex is visited during the same call of dfs.
Code is corrected.

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thank you, but how's the call of this dfs ? ~~~~~ for(i = 0; i < n; i++) if(!vis[i]) dfs(i, i) ~~~~~

    ?

    → Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    what is the significance of "u != parent" and checking "vis[u]" in if condition ?

    → Reply
»
12 years ago, # |
← Rev. 4   Vote: I like it 0 Vote: I do not like it

Use the following approach: consider we have three colors, and each vertex should be painted with one of these colors. "White color" means that the vertex hasn't been visited yet. "Gray" means that we've visited the vertex but haven't visited all vertices in its subtree. "Black" means we've visited all vertices in subtree and left the vertex. So, initially all vertices are white. When we visit the vertex, we should paint it gray. When we leave the vertex (that is we are at the end of the dfs() function, after going throung all edges from the vertex), we should paint it black. If you use that approach, you just need to change dfs() a little bit. Assume we are going to walk through the edge v->u. If u is white, go there. If u is black, don't do anything. If u is gray, you've found the cycle because you haven't left u yet (it's gray, not black), but you come there one more time after walking throung some path.

To keep vertices' colors replace boolean array with char or integer array and just use values in range [0..2].

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Instead of using vis array, maintain a status array with 3 states: 0-unprocessed, 1-processing, 2-processed. If during the traversal you encounter a child with state 1 then there exists a cycle.

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

In each step, delete the sources of your graph. if there wasn't any, stop the loop. and at last check if your array of vertices is of size n or not, if it isn't then you have a cycle.

→ Reply