3

I have to find the number of cycles in a graph.

I know Tarjan's strongly connected components algorithm but i have a little bit confusion.

Can I use DFS or BFS to find the number of cycles.Why Not.If IT's is tree will the answer will change

I am asking if there is only one outgoing edge from each node can i use dfs.

Narendra Modi
  • 851
  • 1
  • 13
  • 29
  • Yes you can use DFS to find the number of cycles of a permutation (which is what a graph represents where every node has out-degree 1) – Niklas B. Sep 21 '15 at 10:27
  • Maybe [this](http://stackoverflow.com/questions/546655/finding-all-cycles-in-graph) helps a little. [This one](http://stackoverflow.com/questions/10232306/using-floyd-warshall-algorithm-to-count-number-of-paths-between-2-vertices) might also be useful. – G. Bach Sep 21 '15 at 19:27

1 Answers1

0

Yes, you can use DFS to find cycles in a graph. There are different types of edges present in graphs, including back edges which are defined as edges that connect a vertex back to one of its previous ancestors in the graph. These are edges that find vertices that had already been discovered in the DFS but not finished yet. By definition, a back edge implies a cycle, so we can use this definition to count the cycles in a graph.

A simple algorithm to do just this involves running DFS and keeping track of discovered vertices in the recursion stack. So, whenever the DFS discovers a new vertex, it is marked as "discovered" and placed onto the stack. It will be taken off the stack as soon as it is "finished" - when all of the vertex's children have been discovered and the DFS has rewound back to that vertex. If a discovered vertex that is not finished and is thus on that stack is discovered later in the DFS, we know there is a back edge and thus a cycle and can increase a counter by 1 or make note of it however you choose.

To your question about if this changes with trees - a tree by definition is a data structure with no cycles. Therefore, we never have to worry about looking for cycles in trees.

I hope this helps!

Jordan
  • 1