### natofp's blog

By natofp, history, 21 month(s) ago,

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.

• -1

 » 21 month(s) ago, # |   0 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.
•  » » 21 month(s) ago, # ^ |   0 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.
•  » » » 4 weeks ago, # ^ |   0 Hi, could you also provide logic using bfs for the cycle detection.
 » 21 month(s) ago, # |   0 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.
 » 21 month(s) ago, # | ← Rev. 2 →   +6 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.
•  » » 21 month(s) ago, # ^ |   +5 This code fails to find a cycle in a graph with two edges : 0-->1 , 1-->0
•  » » » 20 months ago, # ^ |   0 Correct, thank you, I think I fixed it now.
•  » » 19 months ago, # ^ |   0 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
•  » » » 19 months ago, # ^ |   0 This is only to determine if a cycle exists, not to count them.
•  » » » » 19 months ago, # ^ |   0 is there any way to find it efficiently ??
 » 21 month(s) ago, # |   +21 Wait...am I color blind or something? Is that a div 1 coder asking this question? Hmm...seems fishy.
•  » » 21 month(s) ago, # ^ |   +3 Plus the fact that expert answered the question.
•  » » 21 month(s) ago, # ^ |   +4 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.
 » 21 month(s) ago, # |   +5 I like the idea of maintaining the "path" using some boolean arrayfor 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 pathif 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.
 » 19 months ago, # |   0 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.
 » 7 months ago, # |   0 Initially all element of stack are assigned zero. Stack switch ON the current root node that was in the recursive stack memory (still not finish the dfs call). so use extra stack array to monitor the current stack. void dfs(int root) { vis[root] = 1; stack[root] = 1; for (auto node: edge[root]) { if(vis[node] == 0 && stack[node] == 0) { dfs(node); } else if(stack[node] == 1) //find the cycle } stack[root] = 0; } 
 » 4 weeks ago, # |   -10 Hi, could you also provide logic using bfs for the cycle detection.
 » 4 weeks ago, # |   0 This is a great video, explaining the exact concept.