Parvej's blog

By Parvej, history, 2 months ago, In English

How can I find all the simple cycles in an undirected graph?

126615260_419079712777006_8560932289449234104_n.png In the picture, there are 3 simple cycle:

  1. 1-2-3

  2. 1-2-4-5

  3. 1-3-2-4-5

How can I print all of them?

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by Parvej (previous revision, new revision, compare).

»
2 months ago, # |
  Vote: I like it +5 Vote: I do not like it

Just try to backtracking/bruteforces. Each vertices during the visit will be marked (not go to that vertice again), else unmark it. The complexity will be $$$O(n!)$$$ time