natofp's blog

Finding cycle in (directed) graph
By natofp, history, 6 years ago, In English

Hi,

can anyone provide a good source, or method to find any cycle in directed graph? The answer should be the list of edges ( pairs of vertices). I did not manage to find anything satisfying enough.

Thanks in advance.

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

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

Use dfs to find cycle, when you find it, just traverse back and when you get to node that you visited last you print the cycle. For example if you do dfs and traverse order is 1 - 2 - 3 - 4 - 5 - 2, then you traverse from back and when you reach 2 for the second time you print the edges. This can be done with one additional array.

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

    I think it is not that simple, that algorithm works on an undirected graph but fails on directed graphs like 

    0-->1
|   |
v   v
2-->3

    The problem is that in your algorithm if you start at 0 then 3 will kinda look like a cycle, even though it's not.

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

The simplest way is just to use DFS from any node. Then during the DFS keep track of how deep in the DFS each node you've visited is (lets call it index), also using recursion keep track of the earliest (least deep) node you've seen or any of your predecessor have seen (lets call it low_link). The idea is that if the index and low_link coincide for any node then you've found a cycle, because one of your predecessors have seen you. If the index and low_link never coincide then none of the nodes you've visited are part of any cycle so remove them from the graph. This is the main idea behind Tarjan's strongly connected components algorithm which does quite a bit more than just finding a cycle.

→ Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it +6 Vote: I do not like it

Use colors, for example, white, grey and black.

void dfs(int v, int p){
  color[v] = 1; // GREY
  for(int w : g[v]){
    if(color[w] == 1){
      // you found a cycle, it's easy to recover it now.
    }
    if(color[w] == 0) dfs(w, v);
  }
  color[v] = 2; // BLACK
}

And then just call it from any white node.

for(int i = 0; i < n; i++)
  if(color[i] == 0) dfs(i, -1); // IF NODE IS WHITE, START NEW DFS

For more information read the CLRS. Specifically, you are interested in knowing what tree edges, back edges, cross edges and forward edges are.

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

    This code fails to find a cycle in a graph with two edges : 0-->1 , 1-->0

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

    for n = 4,m = 6 1->2 2->4 4->3 3->1 3->2 2->3 this alog gives only 2 cycles but we have 3

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

      This is only to determine if a cycle exists, not to count them.

      → Reply
»
6 years ago, # |
  Vote: I like it +21 Vote: I do not like it

Wait...am I color blind or something? Is that a div 1 coder asking this question? Hmm...seems fishy.

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

    Plus the fact that expert answered the question.

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

    You don't really need to know many algorithms to reach 1900. If you look at his recent contests you'll see that he consistently and quickly solves non-technical problems.

    → Reply
»
6 years ago, # |
  Vote: I like it +5 Vote: I do not like it

I like the idea of maintaining the "path" using some boolean array

for example, you might has vis[n] and then in_path[n] do check whether a) the node has been visited or b) whether the node is in your current path

if you hit something already in your path then you've hit a cycle. To actually get to cycle you want to keep a stack with the actual path.

For example, we are at node u and we hit node v, which is already in path. Then we know u is in the path, and we look backwards in the stack until we hit v.

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

you can use something like topological sort. after doing top sort some nodes will remain. You can just do a dfs, eventually you will reach to your starting node.

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

This is a great video, explaining the exact concept.

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

International Grandmaster doesn't know such a basic stuff. Kinda sus

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

    he was not igm when he asked that question, he was a purple like you :)

    → Reply