Will DFS from every node give all cycles in a directed graph

Question

I want to find all the cycles in a directed graph. Starting Depth-first search from one node will find some cycles(finding back-edges). So, i applied dfs to all the nodes in the graph(i.e. each time the root is a different node). I am able to get all the cycles using this(by eliminating duplicate ones). But, i am not sure whether this will work for all graphs and whether this is correct approach or not. Can anyone suggest me whether this works in all situations.

Thanks

You must be very careful because cycles occur as a combination of forward, cross, back and tree edges, is not trivial to code a solution for handling all possibilities. I have been looking on this approach for long and finally left it for an other solution, I have already coded in php, check here: http://stackoverflow.com/a/9665400/642173 — Melsi, Mar 18 '12 at 23:52

score 0 · Answer 1 · answered Apr 13 '13 at 04:11

The answer is NO! Because running DFS on all the nodes indicates a polynomial time algorithm. And there is no polynomial time algorithm exists to find all the cycles in a directed graph.

Consider such case, suppose you have a complete graph with n nodes(every node points to all the rest nodes), then each non-empty subset of this n nodes indicates a cycle. There are 2^n -1 number of such subsets, so no way to find exponential number of cycles in a polynomial time.

score 0 · Answer 2 · answered Jun 25 '10 at 07:08

If you have disconnected nodes (the graph is not connected) then you will have to traverse the graph from each node. It won't matter if you use DFS or BFS as you are not stopping your traversal upon finding a particular node.

I would keep a global VisitedNodes list so you don't have to do full traversals from already visited nodes instead of your usual "Per-Path" ancestor list to avoid cycles.

Will DFS from every node give all cycles in a directed graph

2 Answers2