在有向圖中找出一個循環中的所有頂點

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，這比第一個恕我直言更好。