如何在有向图中找到(迭代)从/到给定节点的所有循环?
How can I find (iterate over) ALL the cycles in a directed graph from/to a given node?
例如,我想要这样的东西:
For example, I want something like this:
A->B->A A->B->C->A但不是:B->C->B
but not: B->C->B
推荐答案我在搜索中找到了这个页面,由于循环与强连通分量不同,我一直在搜索,最后,我找到了一个有效的算法,列出了所有有向图的(基本)循环.它来自 Donald B. Johnson,该论文可以在以下链接中找到:
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:
www.cs.tufts.edu/comp/150GA/homeworks/hw1/Johnson%2075.PDF
可以在以下位置找到 Java 实现:
A java implementation can be found in:
normalisiert.de/code/java/elementaryCycles.zip
约翰逊算法的Mathematica演示可以在这里找到,实现可以从右侧下载(下载作者代码").
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:
dx.doi/10.1137/0205007
根据文章,约翰逊的算法是最快的.
According to the article, Johnson's algorithm is the fastest one.
更多推荐
查找有向图中的所有循环
发布评论