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

您应该寻找基本循环，其中没有顶点（除了开始/结束）出现不止一次。在这种情况下，有线性时间算法（节点+边缘线性）。例如，参见http://www.cs.tufts.edu/comp/150GA/homeworks/hw1/Johnson%2075.PDF 。这来自在有向图中查找所有循环的第二个答案，这比第一个恕我直言要好。