graph - 有向グラフのサイクル内のすべての頂点を見つける

Question

私は有向グラフ、つまり次数 nx n の行列を持っています。
サイクルに含まれる頂点とともに、そこに存在するすべてのサイクルを見つける必要があります。

次に例を示します。

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

出力は次のようになります。

 No.of cycles found : 4  
 A->B->A  
 A->B->C->A
 A->C->A
 A->D->A

Answer 1

頂点 (begin/end 以外) が複数回出現しない基本サイクルを探す必要があります。その場合、線形時間アルゴリズム (ノード + エッジで線形) があります。たとえば、http://www.cs.tufts.edu/comp/150GA/homeworks/hw1/Johnson%2075.PDFを参照してください。これは、有向グラフですべてのサイクルを見つける の2番目の回答から来ています。これは、最初のIMHOよりも優れています。