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

Question

Hi, 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

Answer 1

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.