CODEWITHSUNDEEP
graphcycle-detection
user3035457
user3035457

Reputation: 33

Find all vertices in a cycle in a directed graph

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

Upvotes: 1

Views: 2312

Answers (1)

Edward Doolittle
Edward Doolittle

Reputation: 4100

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.

Upvotes: 0

Related Questions