1

The problem is as the title suggests, the graph is given in Adjacency List Form. My approach is to call DFS in any one vertex and whenever I hit a visited vertex during my DFS recursive step I increment the counter of a global variable starting from 0 and do not call DFS for that visited vertex (as we do in general). Is this going to work, am I thinking right ? I haven't found any relevant article in the internet as well to learn about #Number of cycles in undirected graph.

Elaboration: I mean to use a simple DFS method. While we do nothing in the recursive step in encountering a visited vertex, I increase the counter global variable value for that situation. I do this, since whenever I am encountering a visited vertex, implies I am completing a cycle. I claim that : every cycle in the graph is encountered only once (atleast and atmost once) in any DFS run. AM I CORRECT IN THIS CLAIM ?

Edit: No back edges

Akash
  • 939
  • 1
  • 8
  • 27
  • I assume you mean number of *simple* cycles? Also, provide more details please, from my understanding of what you propose, you will also increment upon discovering a *cross edge* – amit Apr 22 '17 at 10:19
  • Ya I mean simple cycle. Please see the elaboration in the question. – Akash Apr 22 '17 at 10:21
  • 2
    [Finding all cycles in undirected graphs.](http://stackoverflow.com/questions/12367801/finding-all-cycles-in-undirected-graphs) – Bernhard Barker Apr 22 '17 at 10:29
  • Thanks @Dukeling – Akash Apr 22 '17 at 10:37

1 Answers1

2

I am sorry to post answer to my answer itself, just for those who have similar doubt in future : I found that I will be counting many cycles redundantly, for eg :- 

    A 
  /   \
B ----- C
  \   /
    D

Starting DFS from A->B->C->D I get the cycle C-B-D counted twice. I also learned the problem for finding all cycles in an undirected graph is np-hard. Bad Luck :'(

Akash
  • 939
  • 1
  • 8
  • 27
  • 2
    `I am sorry to post answer to my answer itself` Don't be. that's perfectly fine: https://stackoverflow.com/help/self-answer – amit Apr 22 '17 at 11:55