如何找到(迭代)有向图中从给定节点到所有节点的所有循环?
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
推荐答案我在搜索中找到了此页面,由于周期与强连接的组件并不相同,因此我一直进行搜索,最后,我找到了一种有效的算法,其中列出了所有有向图的(基本)循环。它来自唐纳德·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
A 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:
http ://dx.doi/10.1137/0205007
根据该文章,约翰逊算法是最快的算法。
According to the article, Johnson's algorithm is the fastest one.
更多推荐
在有向图中找到所有循环
发布评论