0

I have a directed graph i.e matrix of order n x n.
I need to find all the cycles present in it along with the vertices involved in the cycle.

Here is an example: 

 A B C D    
 0 1 1 1    
 1 0 1 0    
 1 0 0 0    
 1 0 0 0

The output should be similar to: 

 No.of cycles found : 4  
 A->B->A  
 A->B->C->A
 A->C->A
 A->D->A
Phantômaxx
  • 37,901
  • 21
  • 84
  • 115
user3035457
  • 23
  • 1
  • 4
  • So what exactly is your question? – ChriPf Apr 17 '15 at 13:03
  • I want algorithm or logic or code to find the vertex list which are involved in the cycle – user3035457 Apr 17 '15 at 13:06
  • This is not possible in poly-time, because if it was then you could solve the Hamiltonian path problem in poly-time, and that problem is NP-complete. More simply, the number of possible cycles is huge, so this is not possible in polynomial time. You might as well brute-force it (try all paths recursively) and record which go back to the source and print those. Sort of like DFS, except you can visit a node more than once. This is going to take a lot of time for graphs of even slightly reasonable size, though, and I'm not sure if there's a way that's faster. – Jimmy Apr 17 '15 at 13:52
  • possible duplicate of [Finding all cycles in graph](http://stackoverflow.com/questions/546655/finding-all-cycles-in-graph) – ChriPf Apr 17 '15 at 13:58

1 Answers1

0

You should be looking for elementary cycles, in which no vertex (other than begin/end) appears more than once. In that case there are linear time algorithms (linear in nodes + edges). See http://www.cs.tufts.edu/comp/150GA/homeworks/hw1/Johnson%2075.PDF, for example. This comes from the second answer at Finding all cycles in a directed graph, which is better than the first IMHO.

Community
  • 1
  • 1
Edward Doolittle
  • 4,002
  • 2
  • 14
  • 27