Блог пользователя aajjbb

How to check cycles inside a Topological Sort
Автор aajjbb, 12 лет назад, По-английски

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 ?

  • Проголосовать: нравится
  • +3
  • Проголосовать: не нравится

»
12 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

→ Ответить
»
12 лет назад, # |
← Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится 
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.

→ Ответить
»
12 лет назад, # |
← Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится

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].

→ Ответить
»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

→ Ответить
»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

→ Ответить