在有向图中找出一个循环中的所有顶点

Question

我有一个有向图，例如n×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。这来自第二个答案Finding all cycles in a directed graph，这比第一个恕我直言更好。