我怎样才能找到（遍历）所有有向图的周期从/给定节点？

How can I find (iterate over) ALL the cycles in a directed graph from/to a given node?

例如，我想是这样的：

A->B->A
A->B->C->A

而不是：     B-> C-> B

but not: B->C->B

推荐答案

我找到了这个网页中搜索与自循环是不一样的强连通分量，我一直在寻找，终于，我发现了一个高效的算法，其中列出了所有有向图中（小学）的周期。距离唐纳德·约翰逊和纸张可以在以下链接：

I found this page in my search and since cycles are not same as strongly connected components, I kept on searching and finally, I found an efficient algorithm which lists all (elementary) cycles of a directed graph. It is from Donald B. Johnson and the paper can be found in the following link:

http://www.cs.tufts.edu/comp/150GA/homeworks/hw1/Johnson%2075.PDF

一个Java实现中可以找到：

A java implementation can be found in:

http://normalisiert.de/$c$c/java/elementaryCycles.zip

A 数学的示范约翰逊的算法可以在这里找到 ，实现可以从下载右（"Download笔者code）。

A Mathematica demonstration of Johnson's algorithm can be found here, implementation can be downloaded from the right ("Download author code").

注：其实，有很多算法针对此问题。其中一些是这篇文章中列出：

Note: Actually, there are many algorithms for this problem. Some of them are listed in this article:

http://dx.doi.org/10.1137/0205007

根据这篇文章，约翰逊的算法是最快的国家之一。

According to the article, Johnson's algorithm is the fastest one.