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

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开发者_JS百科 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

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.

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.